Talk:ALGOL 68-primes: Difference between revisions
→Source code: Added PROC is probably prime
(→Source code: Added operators, etc. for extracting a list of primes from a sieve of primes) |
(→Source code: Added PROC is probably prime) |
||
Line 1:
===Source code===
Note the is probably prime PROC is based on code from [https://www.rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test The Miller–Rabin primality test task] and the [https://www.rosettacode.org/wiki/ALGOL_68/prelude prelude].
<lang algol68># primes.incl.a68: prime related operators, procedure etc. #
Line 69 ⟶ 71:
OP FROMPRIMESIEVE = ( PRIMEEXTRACT ex, []BOOL prime )[]INT: ex PRIMESFROMSIEVE prime;
PROC is probably prime = ( LONG LONG INT n )BOOL:
IF n = 2 THEN TRUE
ELIF NOT ODD n THEN FALSE
ELIF n < 3 THEN FALSE
ELIF n < 10 000 THEN
# smallish number = use trial division #
BOOL is prime := TRUE;
FOR i FROM 3 BY 2 TO ENTIER sqrt( SHORTEN SHORTEN n ) WHILE is prime := n MOD i /= 0 DO SKIP OD;
is prime
ELSE
# miller rabin primality test #
PROC pow mod = (LONG LONG INT b, in e, modulus)LONG LONG INT:
BEGIN
LONG LONG INT sq := b, e := in e;
LONG LONG INT result := IF ODD e THEN b ELSE 1 FI;
e OVERAB 2;
WHILE e /= 0 DO
sq := sq * sq MOD modulus;
IF ODD e THEN result := result * sq MOD modulus FI ;
e OVERAB 2
OD;
result
END # pow mod # ;
INT k = 10;
LONG LONG INT d := n - 1;
INT s := 0;
WHILE NOT ODD d DO
d OVERAB 2;
s +:= 1
OD;
BOOL is prime := TRUE;
TO k WHILE is prime DO
LONG LONG INT a := 2 + ENTIER ( random * ( n - 3 ) );
LONG LONG INT x := pow mod( a, d, n );
IF x /= 1 THEN
BOOL done := FALSE;
TO s WHILE NOT done DO
IF x = n - 1
THEN done := TRUE
ELSE x := x * x MOD n
FI
OD;
IF NOT done THEN IF x /= n-1 THEN is prime := FALSE FI FI
FI
OD;
is prime
FI # is probably prime # ;
# END primes.incl.a68 #</lang>
| |||