Lucas-Lehmer test: Difference between revisions

Content added Content deleted
(Clojure version added by Lau Jensen)
m (Fixed lang tags.)
Line 40: Line 40:
=={{header|ALGOL 68}}==
=={{header|ALGOL 68}}==
{{works with|algol68g-mk11}}
{{works with|algol68g-mk11}}
main:(
<lang algol68>main:(
PRAGMAT stack=1M precision=20000 PRAGMAT
PRAGMAT stack=1M precision=20000 PRAGMAT

⚫
PROC is prime = ( INT p )BOOL:
PROC is prime = ( INT p )BOOL:
IF p = 2 THEN TRUE
IF p = 2 THEN TRUE
ELIF p <= 1 OR p MOD 2 = 0 THEN FALSE
ELIF p <= 1 OR p MOD 2 = 0 THEN FALSE
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
FI;
FI;

PROC is mersenne prime = ( INT p )BOOL:
PROC is mersenne prime = ( INT p )BOOL:
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 ** 2 - 2) MOD m p
s := (s ** 2 - 2) MOD m p
OD;
OD;
s = 0
s = 0
FI;
FI;

INT upb prime = ( long long bits width - 1 ) OVER 2; # no unsigned #
INT upb prime = ( long long bits width - 1 ) OVER 2; # no unsigned #
INT upb count = 45; # find 45 mprimes if INT has enough bits #
INT upb count = 45; # find 45 mprimes if INT has enough bits #

printf(($" Finding Mersenne primes in M[2.."g(0)"]: "l$,upb prime));
printf(($" Finding Mersenne primes in M[2.."g(0)"]: "l$,upb prime));

INT count:=0;
INT count:=0;
FOR p FROM 2 TO upb prime WHILE
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
count +:= 1
FI
FI
FI;
FI;
count <= upb count
count <= upb count
DO SKIP OD
DO SKIP OD
⚫
)</lang>
)
Output:
Output:
Finding Mersenne primes in M[2..33252]:
<lang algol68>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</lang>
See also: http://www.xs4all.nl/~jmvdveer/mersenne.a68.html
See also: http://www.xs4all.nl/~jmvdveer/mersenne.a68.html


Line 203: Line 203:


=={{header|Clojure}}==
=={{header|Clojure}}==
<lang clojure>
<lang lisp>(defn prime? [i]
(defn prime? [i]
(cond (< i 4) (>= i 2)
(cond (< i 4) (>= i 2)
(zero? (rem i 2)) false
(zero? (rem i 2)) false
Line 216: Line 215:
(recur (inc n) (rem (- (* s s) 2) mp)))))))
(recur (inc n) (rem (- (* s s) 2) mp)))))))


(filter mersenne? (filter prime? (iterate inc 1)))
(filter mersenne? (filter prime? (iterate inc 1)))</lang>
⚫
</lang>
Output:
Output:
Infinite list of Mersenne primes:
Infinite list of Mersenne primes:
Line 227: Line 225:
{{works with|Fortran|90 and later}}
{{works with|Fortran|90 and later}}
Only Mersenne number with prime exponent can be themselves prime but for the small numbers used in this example it was not worth the effort to include this check. As the size of the exponent increases this becomes more important.
Only Mersenne number with prime exponent can be themselves prime but for the small numbers used in this example it was not worth the effort to include this check. As the size of the exponent increases this becomes more important.
<lang fortran> PROGRAM LUCAS_LEHMER
<lang fortran>PROGRAM LUCAS_LEHMER
IMPLICIT NONE
IMPLICIT NONE

INTEGER, PARAMETER :: i64 = SELECTED_INT_KIND(18)
INTEGER, PARAMETER :: i64 = SELECTED_INT_KIND(18)
INTEGER(i64) :: s, n
INTEGER(i64) :: s, n
INTEGER :: i, exponent
INTEGER :: i, exponent
⚫
DO exponent = 2, 31
⚫
IF (exponent == 2) THEN
⚫
s = 0
⚫
ELSE
⚫
s = 4
⚫
END IF
⚫
n = 2_i64**exponent - 1
⚫
DO i = 1, exponent-2
⚫
s = MOD(s*s - 2, n)
⚫
END DO
⚫
IF (s==0) WRITE(*,"(A,I0,A)") "M", exponent, " is PRIME"
⚫
END DO
⚫
DO exponent = 2, 31
⚫
END PROGRAM LUCAS_LEHMER</lang>
⚫
IF (exponent == 2) THEN
⚫
s = 0
⚫
ELSE
⚫
s = 4
⚫
END IF
⚫
n = 2_i64**exponent - 1
⚫
DO i = 1, exponent-2
⚫
s = MOD(s*s - 2, n)
⚫
END DO
⚫
IF (s==0) WRITE(*,"(A,I0,A)") "M", exponent, " is PRIME"
⚫
END DO
⚫
⚫
END PROGRAM LUCAS_LEHMER</lang>


=={{header|Haskell}}==
=={{header|Haskell}}==
Line 362: Line 360:
=={{header|Oz}}==
=={{header|Oz}}==
Oz's multiple precision number system use GMP core.
Oz's multiple precision number system use GMP core.
<lang ocaml>%% compile : ozc -x <file.oz>
<lang oz>%% compile : ozc -x <file.oz>
functor
functor
import
import
Line 483: Line 481:
be smaller than 1000.
be smaller than 1000.


⚫
<lang pop11>define Lucas_Lehmer_Test(p);
<pre>
⚫
define Lucas_Lehmer_Test(p);
lvars mp = 2**p - 1, sn = 4, i;
lvars mp = 2**p - 1, sn = 4, i;
for i from 2 to p - 1 do
for i from 2 to p - 1 do
Line 500: Line 497:
endif;
endif;
p + 2 -> p;
p + 2 -> p;
endwhile;
endwhile;</lang>

</pre>


The output (obtained in few seconds) is:
The output (obtained in few seconds) is:
<lang pop11>M2
<pre>
M2
M3
M3
M5
M5
Line 519: Line 513:
M127
M127
M521
M521
M607
M607</lang>
</pre>


=={{header|Python}}==
=={{header|Python}}==
Line 565: Line 558:


=={{header|Ruby}}==
=={{header|Ruby}}==
<lang python>def is_prime ( p )
<lang ruby>def is_prime ( p )
if p == 2
if p == 2
return true
return true
Retrieved from "https://rosettacode.org/wiki/Lucas-Lehmer_test"