Talk:ALGOL 68-primes: Difference between revisions
→Source code: primes.incl.a68 - horrendous bug fix
(→Source code: Added PROC is probably prime) |
(→Source code: primes.incl.a68 - horrendous bug fix) |
||
(6 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>
# 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 # ;
# returns an approximate size of sieve required for n primes #
# END primes.incl.a68 #</lang>▼
# uses Chebyshev's formula of n/ln(n), increased by 20% #
# as n/ln(n) is only pi(n) when n appraoches infinity #
OP APPROXIMATESIEVESIZEFOR = ( INT n )INT:
BEGIN
INT result := 10;
WHILE INT prime count = ENTIER ( ( result / ln( result ) ) * 1.2 );
prime count < n
DO
result *:= 4
OD;
result
END # APPROXIMATESIEVESIZEFOR # ;
</syntaxhighlight>
|