Talk:ALGOL 68-primes: Difference between revisions
Content added Content deleted
(lang -> syntaxhighlight) |
(→Source code: Improved is probably prime) |
||
| 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 = 2 THEN TRUE |
IF n = 2 THEN TRUE |
||
ELIF NOT ODD n THEN FALSE |
ELIF NOT ODD n THEN FALSE |
||
ELIF n < 3 THEN FALSE |
ELIF n < 3 THEN FALSE |
||
ELIF n |
ELIF n MOD 3 = 0 THEN FALSE |
||
ELIF n MOD 5 = 0 THEN FALSE |
|||
ELIF n MOD 7 = 0 THEN FALSE |
|||
ELIF n MOD 11 = 0 THEN FALSE |
|||
ELIF n < 10 000 000 THEN |
|||
# smallish number = use trial division # |
# smallish number = use trial division # |
||
BOOL is prime := TRUE; |
BOOL is mr prime := TRUE; |
||
FOR i FROM 3 BY 2 TO ENTIER sqrt( SHORTEN SHORTEN n ) WHILE is prime := n MOD i /= 0 DO SKIP OD; |
FOR i FROM 3 BY 2 TO ENTIER sqrt( SHORTEN SHORTEN n ) WHILE is mr prime := n MOD i /= 0 DO SKIP OD; |
||
is prime |
is mr prime |
||
ELSE |
ELSE |
||
# miller rabin primality test # |
# miller rabin primality test # |
||
| Line 101: | Line 106: | ||
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 118: | ||
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 129: | ||
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> |
|||