How does this regex find primes? [duplicate]

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.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)