Lucas-Lehmer test: Difference between revisions
Content added Content deleted
m (typo) |
m (→{{header|ALGOL 68}}: missed special case of an even prime) |
||
Line 7: | Line 7: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
main:( |
main:( |
||
PR precision=6800 |
PR precision=6800 PR |
||
PROC is prime = ( INT |
PROC is prime = ( INT p )BOOL: |
||
IF p = 2 THEN TRUE |
|||
( |
|||
ELIF p <= 1 OR p MOD 2 = 0 THEN FALSE |
|||
ELIF n <= 1 OR n MOD 2 = 0 THEN FALSE |
|||
ELSE |
ELSE |
||
BOOL prime := TRUE; |
BOOL prime := TRUE; |
||
FOR i FROM 3 BY 2 TO ENTIER sqrt( |
FOR i FROM 3 BY 2 TO ENTIER sqrt(p) WHILE prime := p MOD i /= 0 DO SKIP OD; |
||
prime |
prime |
||
FI |
FI; |
||
); |
|||
PROC is mersenne prime = ( INT p )BOOL: |
PROC is mersenne prime = ( INT p )BOOL: |
||
IF p = 2 THEN TRUE |
|||
( |
|||
⚫ | |||
LONG LONG INT m p = LONG LONG 2 ** p - 1, LONG LONG INT s := 4; |
LONG LONG INT m p = LONG LONG 2 ** p - 1, LONG LONG INT s := 4; |
||
FROM 3 TO p DO |
|||
FROM 3 TO p DO |
|||
s := (s * s - 2) MOD m p |
|||
⚫ | |||
OD; |
|||
s = 0 |
|||
FI; |
|||
printf($" Mersenne primes: "l$); |
printf($" Mersenne primes: "l$); |
||
INT upb=ROUND(log(10)/log(2)*10000000); |
|||
FOR p FROM 1 BY 2 TO 33219281 DO |
|||
FOR p FROM 2 TO upb DO |
|||
IF is prime(p) THEN |
|||
IF is mersenne prime(p) THEN |
|||
printf (($" M"g(0)$,p)) |
printf (($" M"g(0)$,p)) |
||
FI |
FI |
Revision as of 06:23, 14 February 2008
Lucas-Lehmer test
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
Lucas-Lehmer Test: for p a prime, the Mersenne number 2**p-1 is prime if 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 the first 45 Mersenne primes.
ALGOL 68
main:( PR precision=6800 PR PROC is prime = ( INT p )BOOL: IF p = 2 THEN TRUE ELIF p <= 1 OR p MOD 2 = 0 THEN FALSE ELSE BOOL prime := TRUE; FOR i FROM 3 BY 2 TO ENTIER sqrt(p) WHILE prime := p MOD i /= 0 DO SKIP OD; prime FI; PROC is mersenne prime = ( INT p )BOOL: IF p = 2 THEN TRUE ELSE LONG LONG INT m p = LONG LONG 2 ** p - 1, LONG LONG INT s := 4; FROM 3 TO p DO s := (s * s - 2) MOD m p OD; s = 0 FI; printf($" Mersenne primes: "l$); INT upb=ROUND(log(10)/log(2)*10000000); FOR p FROM 2 TO upb DO IF is prime(p) THEN IF is mersenne prime(p) THEN printf (($" M"g(0)$,p)) FI FI OD )
Output:
Mersenne primes: 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 M44497 M86243 M110503 M132049 M216091 M756839 M859433 M1257787 M1398269 M2976221 M3021377 M6972593 M13466917 M20996011 M24036583 M25964951 M30402457 M32582657 M33219281