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
! 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? 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'.
xx+? makes the plus
so that we start by testing small numbers first 2, 3 ... ('xx', 'xxx' ...),
and the parenteses
(xx+?) remember the matched number for later use.
\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.
It works. That's about it, but it's fun!