Mizblog

http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

The way it works in checking if n is prime is to make n copies of some character. (The original article uses 1’s to confuse us with the \1 pattern match, so I’ll use “x” instead.) It first trivially checks for 0 or 1 of those (0 and 1 are not prime). Then it checks for (xx+?)\1+ which will iterate over successively minimal matches of two or more x’s, and then see if the remaining x’s can be matched by copies of that minimal match from the beginning. If it can be matched, the number was obviously not prime (we just divided it into some unknown number of equal segments). If it can’t be matched, it tries the next most minimal initial matching.

As an example, let’s take 15. We create the test pattern “xxxxxxxxxxxxxxx” and run it through its paces to see if it matches our composite pattern.

• Does it match “” or “x”? Nope.
• Does it match “xx”\1+? Hmm. “xx” “xx” “xx” “xx” “xx” “xx” “xx” “x” Nope!
• Does it match “xxx”\1+? “xxx” “xxx” “xxx” “xxx” “xxx” YES! NOT PRIME!

If we used 17 instead, we’d never find any substring that could be repeated to match the rest of the pattern, and our match would fail, meaning that 17 is prime!