Talk:ALGOL 68-primes: Difference between revisions
Undo revision 342491
(→Source code: Improved is probably prime) |
(Undo revision 342491) Tag: Undo |
||
Line 3:
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].
<syntaxhighlight lang=algol68># primes.incl.a68: prime related operators, procedure etc. #
# returns a sieve of primes up to n #
Line 73 ⟶ 72:
PROC is probably prime = ( LONG LONG INT n )BOOL:
IF n = 2
ELIF NOT ODD n
ELIF n < 3
ELIF n
# smallish number = use trial division #
BOOL is
FOR i FROM 3 BY 2 TO ENTIER sqrt( SHORTEN SHORTEN n ) WHILE is
is
ELSE
# miller rabin primality test #
Line 106 ⟶ 101:
s +:= 1
OD;
BOOL is
TO k WHILE is
LONG LONG INT a := 2 + ENTIER ( random * ( n - 3 ) );
LONG LONG INT x := pow mod( a, d, n );
Line 118 ⟶ 113:
FI
OD;
IF NOT done THEN IF x /= n-1 THEN is
FI
OD;
is
FI # is probably prime # ;
Line 129 ⟶ 124:
OP APPROXIMATESIEVESIZEFOR = ( INT n )INT:
BEGIN
INT result := 10;
WHILE INT
DO
result *:= 4
OD;
result
END # APPROXIMATESIEVESIZEFOR # ;
# END primes.incl.a68 #</syntaxhighlight>▼
▲# END primes.incl.a68 #
| |||