Lucas-Lehmer test: Difference between revisions
Content added Content deleted
(→{{header|C}}: using 64bit unsigned ints and using maximums from <limits.h>) |
m (tidy declarations/copy edit.) |
||
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 |
The following programs calculate all Mersenne primes up to the implementation precision. |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Interpretor: algol68g-mk11 |
|||
main:( |
main:( |
||
PRAGMAT stack=1M precision=20001 PRAGMAT |
PRAGMAT stack=1M precision=20001 PRAGMAT |
||
Line 22: | Line 22: | ||
IF p = 2 THEN TRUE |
IF p = 2 THEN TRUE |
||
ELSE |
ELSE |
||
LONG LONG INT m p = LONG LONG 2 ** p - 1, |
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 29: | Line 29: | ||
FI; |
FI; |
||
INT upb = |
INT upb = ENTIER(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)); |
printf(($" Finding Mersenne primes in M[2.."g(0)"]: "l$,upb)); |
||
Line 58: | Line 58: | ||
else { |
else { |
||
BOOL prime = TRUE; |
BOOL prime = TRUE; |
||
int to = sqrt(p); |
const int to = sqrt(p); |
||
int i; |
int i; |
||
for(i = 3; i <= to; i+=2) |
for(i = 3; i <= to; i+=2) |
||
Line 69: | Line 69: | ||
if( p == 2 ) return TRUE; |
if( p == 2 ) return TRUE; |
||
else { |
else { |
||
long long unsigned m_p = ( 1LLU << p ) - 1; |
const long long unsigned m_p = ( 1LLU << p ) - 1; |
||
long long unsigned s = 4; |
long long unsigned s = 4; |
||
int i; |
int i; |
||
Line 82: | Line 82: | ||
int main(int argc, char **argv){ |
int main(int argc, char **argv){ |
||
int upb = log2l(ULLONG_MAX)/2; |
const int upb = log2l(ULLONG_MAX)/2; |
||
int p; |
int p; |
||
printf(" Mersenne primes:\n"); |
printf(" Mersenne primes:\n"); |
Revision as of 17:08, 15 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 all Mersenne primes up to the implementation precision.
ALGOL 68
Interpretor: algol68g-mk11
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, s := 4; FROM 3 TO p DO s := (s * s - 2) MOD m p OD; s = 0 FI; INT upb = ENTIER(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; const 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 { const 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){ const 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