Lucas-Lehmer test: Difference between revisions
Content deleted Content added
No edit summary |
→{{header|C}}: using 64bit unsigned ints and using maximums from <limits.h> |
||
Line 7:
=={{header|ALGOL 68}}==
main:(
PROC is prime = ( INT p )BOOL:
Line 14:
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;
Line 28 ⟶ 29:
FI;
INT upb = ROUND(SHORTEN long log(SHORTEN LONG LONG REAL(long long max int))/log(2)/2);
printf($" Mersenne primes: "l$);▼
printf(($" Finding Mersenne primes in M[2.."g(0)"]: "l$,upb));
FOR p FROM 2 TO upb DO
IF is prime(p) THEN
Line 39 ⟶ 42:
)
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
=={{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
| |||