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

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

 require 'mathn'
 38749711234868463.prime?
 => false

Answer 3

require 'prime'

Prime.prime?(4)
# => false

Prime.prime?(5)
# => true

Or:

require 'prime'

Prime.instance.prime?(4)
# => false

Prime.instance.prime?(5)
# => true

Answer 4

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 5

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 6

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

Answer 7

If the length of a string of 1's is composite, then the string can be decomposed into multiple identical substrings, like 111111 -> 11 11 11

For example, 1111111111, has 10 1's, and it matches (11){5} or (11111){2}, where {2} means repeated 2 times. 111111111, has 9 1's, and it matches (111){3}.

By generalizing the count of 1's and the number in {}, the regexp is /(1{2,}){2,}/. However, 1{2,} can also be written as 11+, and (...){2,} can be rewritten as (...)\1+, with backreferences.

The ^1?$ part in the first alternation checks for 0 and 1-cases.