Re:My favorite regex of all time
by mvzink on Monday November 12, 2012 @06:37PM
(#4775395)
I had to prove that in a formal languages class once and I still have no idea how it works.
[ Parent
| on HN ]
First, it does not match "prime numbers". It matches composite numbers in unary notation (n is represented by n '1' characters).
The first part (^1?$) allows "" and "1" to match (so that 1 is not detected as a prime).
The second part matches groups of two or more ones (11+?), repeated twice or more, ie products n*m, n ≥ 2, m ≥ 2.
The backreference means that \1 should match the exact same string as the first (11+?). It's different from using (11+?){2,} which would match n_1+n_2+n_3..., n_1 ≥ 2, n_2 ≥ 2, n_3 ≥ 2 (where submatch is independent).