Lucas-Lehmer test: Difference between revisions
Content added Content deleted
No edit summary |
(→{{header|C}}: using 64bit unsigned ints and using maximums from <limits.h>) |
||
Line 7: | Line 7: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
main:( |
main:( |
||
PRAGMAT stack=1M precision=20001 PRAGMAT |
|||
PROC is prime = ( INT p )BOOL: |
PROC is prime = ( INT p )BOOL: |
||
Line 14: | Line 14: | ||
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; |
|||
prime |
prime |
||
FI; |
FI; |
||
Line 28: | Line 29: | ||
FI; |
FI; |
||
INT upb = ROUND(SHORTEN long log(SHORTEN LONG LONG REAL(long long max int))/log(2)/2); |
|||
⚫ | |||
INT upb = ROUND(log(10)/log(2)*10 000 000); |
|||
printf(($" Finding Mersenne primes in M[2.."g(0)"]: "l$,upb)); |
|||
FOR p FROM 2 TO upb DO |
FOR p FROM 2 TO upb DO |
||
IF is prime(p) THEN |
IF is prime(p) THEN |
||
Line 39: | Line 42: | ||
) |
) |
||
Output: |
Output: |
||
Mersenne primes: |
Finding Mersenne primes in M[2..33253]: |
||
M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 |
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 |
||
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 |
|||
See also: http://www.xs4all.nl/~jmvdveer/mersenne.a68.html |
See also: http://www.xs4all.nl/~jmvdveer/mersenne.a68.html |
||
=={{header|C}}== |
|||
#include <math.h> |
|||
#include <stdio.h> |
|||
#include <limits.h> |
|||
#pragma precision=log10l(ULLONG_MAX)/2 |
|||
typedef enum { FALSE=0, TRUE=1 } BOOL; |
|||
BOOL is_prime( int p ){ |
|||
if( p == 2 ) return TRUE; |
|||
else if( p <= 1 || p % 2 == 0 ) return FALSE; |
|||
else { |
|||
BOOL prime = TRUE; |
|||
int to = sqrt(p); |
|||
int i; |
|||
for(i = 3; i <= to; i+=2) |
|||
if (!(prime = p % i))break; |
|||
return prime; |
|||
} |
|||
} |
|||
BOOL is_mersenne_prime( int p ){ |
|||
if( p == 2 ) return TRUE; |
|||
else { |
|||
long long unsigned m_p = ( 1LLU << p ) - 1; |
|||
long long unsigned s = 4; |
|||
int i; |
|||
for (i = 3; i <= p; i++){ |
|||
s = (s * s - 2); |
|||
s = s % m_p; |
|||
} |
|||
return s == 0; |
|||
} |
|||
} |
|||
int main(int argc, char **argv){ |
|||
int upb = log2l(ULLONG_MAX)/2; |
|||
int p; |
|||
⚫ | |||
for( p = 2; p <= upb; p += 1 ){ |
|||
if( is_prime(p) && is_mersenne_prime(p) ){ |
|||
printf (" M%u",p); |
|||
} |
|||
} |
|||
printf("\n"); |
|||
} |
|||
Compiler version: gcc version 4.1.2 20070925 (Red Hat 4.1.2-27)<br> |
|||
Compiler options: gcc -std=c99 -lm Lucas-Lehmer_test.c -o Lucas-Lehmer_test<br> |
|||
Output: |
|||
Mersenne primes: |
|||
M2 M3 M5 M7 M13 M17 M19 M31 |
Revision as of 16:51, 15 February 2008
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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:( PRAGMAT stack=1M precision=20001 PRAGMAT 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; INT upb = ROUND(SHORTEN long log(SHORTEN LONG LONG REAL(long long max int))/log(2)/2); printf(($" Finding Mersenne primes in M[2.."g(0)"]: "l$,upb)); 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:
Finding Mersenne primes in M[2..33253]: 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
C
#include <math.h> #include <stdio.h> #include <limits.h> #pragma precision=log10l(ULLONG_MAX)/2 typedef enum { FALSE=0, TRUE=1 } BOOL; BOOL is_prime( int p ){ if( p == 2 ) return TRUE; else if( p <= 1 || p % 2 == 0 ) return FALSE; else { BOOL prime = TRUE; int to = sqrt(p); int i; for(i = 3; i <= to; i+=2) if (!(prime = p % i))break; return prime; } } BOOL is_mersenne_prime( int p ){ if( p == 2 ) return TRUE; else { long long unsigned m_p = ( 1LLU << p ) - 1; long long unsigned s = 4; int i; for (i = 3; i <= p; i++){ s = (s * s - 2); s = s % m_p; } return s == 0; } } int main(int argc, char **argv){ int upb = log2l(ULLONG_MAX)/2; int p; printf(" Mersenne primes:\n"); for( p = 2; p <= upb; p += 1 ){ if( is_prime(p) && is_mersenne_prime(p) ){ printf (" M%u",p); } } printf("\n"); }
Compiler version: gcc version 4.1.2 20070925 (Red Hat 4.1.2-27)
Compiler options: gcc -std=c99 -lm Lucas-Lehmer_test.c -o Lucas-Lehmer_test
Output:
Mersenne primes: M2 M3 M5 M7 M13 M17 M19 M31