Talk:ALGOL 68-primes: Difference between revisions
→Source code: primes.incl.a68 - horrendous bug fix
(lang -> syntaxhighlight) |
(→Source code: primes.incl.a68 - horrendous bug fix) |
||
| (3 intermediate revisions by the same user not shown) | |||
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 72 ⟶ 73:
PROC is probably prime = ( LONG LONG INT n )BOOL:
IF n
ELIF NOT ODD n THEN FALSE
ELIF n
ELIF n
ELIF n MOD
ELIF n MOD 11
ELIF n < 10 000 000 THEN
INT f := 13;
INT f2 := 169;
INT to next := 56;
BOOL is mr prime := TRUE;
WHILE f2 <= n AND is mr prime DO
is mr prime := short n MOD f /= 0;
f +:= 2;
f2 +:= to next;
to next +:= 8
OD;
is mr prime
ELSE
# miller rabin primality test #
Line 101 ⟶ 113:
s +:= 1
OD;
BOOL is mr prime := TRUE;
TO k WHILE is mr prime DO
LONG LONG INT a := 2 + ENTIER ( random * ( n - 3 ) );
LONG LONG INT x := pow mod( a, d, n );
Line 113 ⟶ 125:
FI
OD;
IF NOT done THEN IF x /= n-1 THEN is mr prime := FALSE FI FI
FI
OD;
is mr prime
FI # is probably prime # ;
Line 124 ⟶ 136:
OP APPROXIMATESIEVESIZEFOR = ( INT n )INT:
BEGIN
prime
END # APPROXIMATESIEVESIZEFOR # ;
# END primes.incl.a68 #
</syntaxhighlight>
| |||