# If number is prime in Ruby using Regexp

At #railsclub @fxn told me about an amazing way of determining wheter the number is prime in different languages – using #regexp! This is really great technique at you can see how simple it is:

```
def isPrimeRegexp n
"1" * n =~ /^1?$|^(11+?)\1+$/
end
```

There are quite a few algorithms for determining wheter the number is prime, there is a good wiki for it. So lets compare #regexp solution to the simplest algorithm using #benchmark_ips:

```
require 'benchmark/ips'
def isPrimeRegexp n
"1" * n =~ /^1?$|^(11+?)\1+$/
end
def isPrime(number)
if number == 0 or number == 1
return false
end
i = 2
limit = number / i
while i < limit
if number % i == 0
return false
end
i += 1
limit = number / i
end
return true
end
Benchmark.ips do |r|
r.report('isPrimeRegexp') do
isPrimeRegexp(131)
end
r.report('isPrime') do
isPrime(131)
end
end
# Calculating -------------------------------------
# isPrimeRegexp 2434 i/100ms
# isPrime 45790 i/100ms
# -------------------------------------------------
# isPrimeRegexp 25621.3 (±1.6%) i/s - 129002 in 5.036280s
# isPrime 898325.9 (±0.7%) i/s - 4533210 in 5.046548s
```

As you can see the regexp solution is not so fast but it is really short and I think that this approach of using regexp for some math is amazing because for many developers regexp is associated to strings and not for working numbers.

@fxn applied this technique for many more #math tricks so you can see all of them at https://github.com/fxn/math-with-regexps.

what about http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ? :-)

@agentcooper, using #Sieve_of_Eratosthenes you generate all the primes below particular number, it is quite different task from determining whether the number is prime.

Remember http://projecteuler.net/ where a lot of programming problems about primes.

They're really quite

similartasks. Running the Sieve for numbers less than the target number gives us the primality of the target, accomplishing the same thing as the regex, and, if we're planning to check a handful of numbers for primality, we see much better performance computing the Sieve once for some upper bound than if we check each number individually.Here's the performance benchmark with the uncached sieve and the cached sieve - and stdlib, for good measure. (In order to test sieve-caching properly, the benchmarks now check a random number up to 1000 on each iteration.)

Here's what I got on my box:

So, while creating a one-off sieve for a single prime test can't even match the performance of the regex, saving largest sieve we've computed so far for future use outperforms even the basic factor checker by a factor of ~1.5. Even if we don't know our upper bound in advance (but we usually do), the sieve is the best approach there is for testing multiple numbers.

Still. Despite being worthless in production, this is hands-down the coolest regex I know :D

@matchu agree and welcome at #gistflow! Thx for such an informative comment! One should usually use some random input when benchmarking with ips.

Heh) I never put this magick in production, but this is great education example for my pupils. Thx)

@ffloyd there is more at https://github.com/fxn/math-with-regexps.