CODEWITHSUNDEEP
rubyregexprimes
Felix F
Felix F

Reputation:

Ruby isPrime Method

('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?

Upvotes: 23

Views: 6746

Answers (7)

rajagopal
rajagopal

Reputation: 49

require 'prime'

Prime.prime?(4)
# => false

Prime.prime?(5)
# => true

Or:

require 'prime'

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

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

Upvotes: 4

Ming-Tang
Ming-Tang

Reputation: 17651

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.

Upvotes: 2

MAK
MAK

Reputation: 26586

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

Upvotes: 1

Trevoke
Trevoke

Reputation: 4117

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

 require 'mathn'
 38749711234868463.prime?
 => false

Upvotes: 20

dland
dland

Reputation: 4419

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 :)

Upvotes: 2

Markus Jarderot
Markus Jarderot

Reputation: 89221

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.

Upvotes: 1

Jay
Jay

Reputation: 42682

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/

Upvotes: 24

Related Questions