Checking for primes with regular expressions?

About a week ago I found an interesting article that describes the the use of a regexp to check for primes in Ruby. It refers to a Perl tricks page which lists Abigail as the original source. So no, this is not from my own head, but since I advocate sensible use of regular expressions*, I decided to give it a go. I first rewrote the original one-liner to CoffeeScript, which proved to be fun on it's own, and got this:

isPrime = (n) -> ! /^x?$|^(xx+?)\1+$/.test (Array n+1).join 'x'

(Array n+1).join 'x' creates a string containing n repetitions of 'x'. The string is then tested agains the regexp. Since the regexp actually matches non-primes we have to negate the result with ! before returning it.

The regular expression itself consists of two parts joined by a pipe. Each part matches a full string from start to finish ^$. When you take away the syntactic sugar you are left with x? and (xx+?)\1+.

x? matches 'x' or an empty string '' to handle border condtions of 1 and 0.


This is where it gets interesting. xx+ matches two or more repetitions of 'x'. The questionmark xx+? makes the plus not greedy so that we start by testing small numbers first 2, 3 ... ('xx', 'xxx' ...), and the parenteses (xx+?) remember the matched number for later use. Then the \1+ matches the previously remembered string one or more times. If it succeeds, it means that the string consists of two or more repetitions of a substring and is therefore not a prime.

So what?

It works. That's about it, but it's fun!

* No, I don't consider this to be a sensible use of regular expressions.