Talk:ALGOL 68-primes: Difference between revisions
Content added Content deleted
(Undo revision 342491) Tag: Undo |
(→Source code: primes.incl.a68 - some improvment to the "is probably prime" procedure.) |
||
Line 3: | 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]. |
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> |
<syntaxhighlight lang=algol68> |
||
# primes.incl.a68: prime related operators, procedure etc. # |
|||
# returns a sieve of primes up to n # |
# returns a sieve of primes up to n # |
||
Line 72: | Line 73: | ||
PROC is probably prime = ( LONG LONG INT n )BOOL: |
PROC is probably prime = ( LONG LONG INT n )BOOL: |
||
IF n |
IF n < 3 THEN n = 2 |
||
ELIF NOT ODD n THEN FALSE |
ELIF NOT ODD n THEN FALSE |
||
ELIF n |
ELIF n MOD 3 = 0 THEN n = 3 |
||
ELIF n |
ELIF n MOD 5 = 0 THEN n = 5 |
||
ELIF n MOD 7 = 0 THEN n = 7 |
|||
ELIF n MOD 11 = 0 THEN n = 11 |
|||
ELIF n < 10 000 000 THEN |
|||
FOR i FROM 3 BY 2 TO ENTIER sqrt( SHORTEN SHORTEN n ) WHILE is prime := n MOD i /= 0 DO SKIP OD; |
|||
INT short n = SHORTEN SHORTEN n; |
|||
INT f := 5; |
|||
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 |
ELSE |
||
# miller rabin primality test # |
# miller rabin primality test # |
||
Line 101: | Line 113: | ||
s +:= 1 |
s +:= 1 |
||
OD; |
OD; |
||
BOOL is prime := TRUE; |
BOOL is mr prime := TRUE; |
||
TO k WHILE is prime DO |
TO k WHILE is mr prime DO |
||
LONG LONG INT a := 2 + ENTIER ( random * ( n - 3 ) ); |
LONG LONG INT a := 2 + ENTIER ( random * ( n - 3 ) ); |
||
LONG LONG INT x := pow mod( a, d, n ); |
LONG LONG INT x := pow mod( a, d, n ); |
||
Line 113: | Line 125: | ||
FI |
FI |
||
OD; |
OD; |
||
IF NOT done THEN IF x /= n-1 THEN is prime := FALSE FI FI |
IF NOT done THEN IF x /= n-1 THEN is mr prime := FALSE FI FI |
||
FI |
FI |
||
OD; |
OD; |
||
is prime |
is mr prime |
||
FI # is probably prime # ; |
FI # is probably prime # ; |
||
Line 124: | Line 136: | ||
OP APPROXIMATESIEVESIZEFOR = ( INT n )INT: |
OP APPROXIMATESIEVESIZEFOR = ( INT n )INT: |
||
BEGIN |
BEGIN |
||
INT result := 10; |
|||
WHILE INT prime count = ENTIER ( ( result / ln( result ) ) * 1.2 ); |
|||
prime count < n |
|||
DO |
|||
result *:= 4 |
|||
OD; |
|||
result |
|||
END # APPROXIMATESIEVESIZEFOR # ; |
END # APPROXIMATESIEVESIZEFOR # ; |
||
# END primes.incl.a68 # |
# END primes.incl.a68 # |
||
</syntaxhighlight> |