Lucas-Lehmer test: Difference between revisions

← Older editNewer edit →
Content deleted Content added
→‎{{header|Scala}}: Parallel processing since 2.8 made it possible for quicker processing.
Line 1,266: Line 1,266:
=={{header|Ruby}}==
=={{header|Ruby}}==
<lang ruby>def is_prime ( p )
<lang ruby>def is_prime ( p )
if p == 2
return true if p == 2
return false if p <= 1 || p.even?
return true
⚫
(3 .. Math.sqrt(p)).step(2) do |i|
elsif p <= 1 || p % 2 == 0
return false
return false if p % i == 0
else
⚫
(3 .. Math.sqrt(p)).step(2) do |i|
⚫
if p % i == 0
return false
end
end
return true
end
end
true
end
end


def is_mersenne_prime ( p )
def is_mersenne_prime ( p )
if p == 2
return true if p == 2
⚫
m_p = ( 1 << p ) - 1
return true
else
s = 4
m_p = ( 1 << p ) - 1
(p-2).times { s = (s ** 2 - 2) % m_p }
s = 4
s == 0
(p-2).times do
s = (s ** 2 - 2) % m_p
end
return s == 0
end
end
end


Line 1,298: Line 1,287:
upb_count = 45 # find 45 mprimes if int was given enough bits #
upb_count = 45 # find 45 mprimes if int was given enough bits #


puts " Finding Mersenne primes in M[2..%d]:"%upb_prime
puts " Finding Mersenne primes in M[2..%d]:" % upb_prime


count = 0
count = 0
for p in 2..upb_prime
for p in 2..upb_prime
if is_prime(p) && is_mersenne_prime(p)
if is_prime(p) && is_mersenne_prime(p)
print "M%d "%p
print "M%d " % p
count += 1
count += 1
end
end
if count >= upb_count
break if count >= upb_count
break
end
end
end
puts</lang>
puts</lang>


{{out}}
Output:
<pre> Finding Mersenne primes in M[2..33218]:
<pre> Finding Mersenne primes in M[2..33218]:
M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209</pre>
M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209</pre>
Retrieved from "https://rosettacode.org/wiki/Lucas-Lehmer_test"