Lucas-Lehmer test: Difference between revisions
Content deleted Content added
→{{header|ALGOL 68}}: calculate all Mersenne primes up to the implementation's max precision, or the 45th Mersenne prime. (Which ever comes first). |
m →{{header|Python}}: straight from A68 ☺ ... python does rather well with arbitary precision, fast too. |
||
Line 188: | Line 188: | ||
} |
} |
||
} |
} |
||
Output: |
Output: |
||
Finding Mersenne primes in M[2..500]: |
Finding Mersenne primes in M[2..500]: |
||
M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 |
M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 |
||
=={{header|Python}}== |
|||
from sys import stdout |
|||
from math import sqrt, log |
|||
fi = od = None |
|||
def is_prime ( p ): |
|||
if p == 2 : return True |
|||
elif p <= 1 or p % 2 == 0 : return False |
|||
else: |
|||
prime = True; |
|||
for i in range(3, int(sqrt(p))+1, 2 ): |
|||
# print "p:",p |
|||
if p % i == 0 : return False |
|||
else: |
|||
return True |
|||
fi |
|||
fi; |
|||
def is_mersenne_prime ( p ): |
|||
if p == 2 : return True |
|||
else: |
|||
m_p = 2 ** p - 1; s = 4; |
|||
for i in range(3, p+1): |
|||
s = (s * s - 2) % m_p |
|||
od; |
|||
return s == 0 |
|||
fi; |
|||
precision = 20000; |
|||
long_long_bits_width = precision / log(2) * log(10); |
|||
upb_prime = int( long_long_bits_width - 1 ) / 2; # no unsigned # |
|||
upb_count = 45; # find 45 mprimes if int has enough bits # |
|||
print ((" Finding Mersenne primes in M[2..%d]: "%upb_prime)); |
|||
count=0; |
|||
for p in range(2, upb_prime+1): |
|||
if is_prime(p) : |
|||
if is_mersenne_prime(p) : |
|||
stdout.write(" M%d"%p); |
|||
stdout.flush(); |
|||
count += 1 |
|||
fi |
|||
fi; |
|||
if count >= upb_count : break; fi |
|||
od |
|||
Output: |
|||
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 |