How does this regex find primes?
primes, regex
Solution
I think the article explains it rather well, but I'll try my hand at it as well.
Input is in unary form. 1 is `1`, 2 is `11`, 3 is `111`, etc. Zero is an empty string.
The first part of the regex matches 0 and 1 as non-prime. The second is where the magic kicks in.
`(11+?)` starts by finding divisors. It starts by being defined as `11`, or 2. `\1` is a variable referring to that previously captured match, so `\1+` determines if the number is divisible by that divisor. (`111111` starts by assigning the variable to `11`, and then determines that the remaining `1111` is `11` repeated, so 6 is divisible by 2.)
If the number is not divisible by two, the regex engine increments the divisor. `(11+?)` becomes `111`, and we try again. If at any point the regex matches, the number has a divisor that yields no remainder, and so the number cannot be prime.
Problem
Possible Duplicate: How to determine if a number is a prime with regex? This page claims that this regular expression discovers non-prime numbers (and by counter-example: primes): ``` /^1?$|^(11+?)\1+$/ ``` How does this find primes?