# 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.

## (xx+?)\1+

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.