Talk:ALGOL 68-primes: Difference between revisions
Content added Content deleted
(→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: | Line 1: | ||
===Source code=== |
===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. # |
<lang algol68># primes.incl.a68: prime related operators, procedure etc. # |
||
Line 69: | Line 71: | ||
OP FROMPRIMESIEVE = ( PRIMEEXTRACT ex, []BOOL prime )[]INT: ex PRIMESFROMSIEVE prime; |
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> |
# END primes.incl.a68 #</lang> |