Lucas-Lehmer test: Difference between revisions
Content added Content deleted
(→{{header|Java}}: Combined code spaces) |
(→{{header|ALGOL 68}}: calculate all Mersenne primes up to the implementation's max precision, or the 45th Mersenne prime. (Which ever comes first).) |
||
| Line 3: | Line 3: | ||
and only if 2**p-1 divides S(p-1) where S(n+1)=S(n)**2-2, and S(1)=4. |
and only if 2**p-1 divides S(p-1) where S(n+1)=S(n)**2-2, and S(1)=4. |
||
The following programs calculate all Mersenne primes up to the implementation |
The following programs calculate all Mersenne primes up to the implementation's |
||
maximium precision, or the 45th Mersenne prime. (Which ever comes first). |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
| Line 44: | Line 45: | ||
Interpretor: algol68g-mk11 |
Interpretor: algol68g-mk11 |
||
main:( |
main:( |
||
PRAGMAT stack=1M precision= |
PRAGMAT stack=1M precision=20000 PRAGMAT |
||
PROC is prime = ( INT p )BOOL: |
PROC is prime = ( INT p )BOOL: |
||
| Line 51: | Line 52: | ||
ELSE |
ELSE |
||
BOOL prime := TRUE; |
BOOL prime := TRUE; |
||
FOR i FROM 3 BY 2 TO ENTIER sqrt(p) |
FOR i FROM 3 BY 2 TO ENTIER sqrt(p) |
||
WHILE prime := p MOD i /= 0 DO SKIP OD; |
WHILE prime := p MOD i /= 0 DO SKIP OD; |
||
prime |
prime |
||
| Line 59: | Line 60: | ||
IF p = 2 THEN TRUE |
IF p = 2 THEN TRUE |
||
ELSE |
ELSE |
||
LONG LONG INT m p = LONG LONG 2 ** p - 1, s := 4; |
LONG LONG INT m p := LONG LONG 2 ** p - 1, s := 4; |
||
FROM 3 TO p DO |
FROM 3 TO p DO |
||
s := (s * s - 2) MOD m p |
s := (s * s - 2) MOD m p |
||
| Line 66: | Line 67: | ||
FI; |
FI; |
||
INT upb = |
INT upb prime = ( long long bits width - 1 ) OVER 2; # no unsigned # |
||
INT upb count = 45; # find 45 mprimes if INT has enough bits # |
|||
printf(($" Finding Mersenne primes in M[2.."g(0)"]: "l$,upb)); |
printf(($" Finding Mersenne primes in M[2.."g(0)"]: "l$,upb prime)); |
||
INT count:=0; |
|||
FOR p FROM 2 TO upb |
FOR p FROM 2 TO upb prime WHILE |
||
IF is prime(p) THEN |
IF is prime(p) THEN |
||
IF is mersenne prime(p) THEN |
IF is mersenne prime(p) THEN |
||
printf (($" M"g(0)$,p)) |
printf (($" M"g(0)$,p)); |
||
count +:= 1 |
|||
FI |
FI |
||
FI |
FI; |
||
count <= upb count |
|||
OD |
|||
DO SKIP OD |
|||
) |
) |
||
Output: |
Output: |
||
Finding Mersenne primes in M[2.. |
Finding Mersenne primes in M[2..33252]: |
||
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 |
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 |
||
See also: http://www.xs4all.nl/~jmvdveer/mersenne.a68.html |
See also: http://www.xs4all.nl/~jmvdveer/mersenne.a68.html |
||