Ruby isPrime Method

Question

('1' * N) !~ /^1?$|^(11+?)\1+$/

On the net, I found this piece of Ruby code that works for N >= 0 that determines whether or not N is a prime. From what I can tell, it looks like play with regex but I have no idea how it works. Could someone tell me how it works?

Answer 1

You can find a lengthy explanation of this code here: http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

Answer 2

Greatest Common Divisor (gcd):

/^(1+)\1*=\1+$/.match('1' * x + '=' + '1' * y)[1].length

Both this and the is_prime one works in about the same way. It tries all combinations before giving up.

This one will try to split the first number in even parts, and match the second number with one or more of those parts. If it finds a match it returns the length of the selected part.

Answer 3

See also What is the most brilliant regex you’ve ever used? (and yes, I can confirm that this regexp was originally written by Abigail. I've even heard her explain how it works :)

Answer 4

This is probably rather off-topic, but in Ruby 1.9, you can do this:

 require 'mathn'
 38749711234868463.prime?
 => false

Answer 5

Yet another blog with a pretty good explanation: Famous Perl One-Liners Explained (part III)

Answer 6

Although the regex is amazing, the runtime doesn't seem to be too great from the tests I've done. Can someone verify this?