Anonymous user
Miller–Rabin primality test: Difference between revisions
→[[Miller-Rabin_test#ALGOL 68]]
(Python added (from bc)) |
|||
Line 21:
* Deterministic variants of the test exist and can be implemented as extra (not mandatory to complete the task)
{{trans|python}}
{{works with|ALGOL 68|Standard - with precludes manually inserted }}
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386 - ELLA has no FORMATted transput, also it generates a call to undefined C LONG externals }} -->
<lang algol>MODE LINT=LONG INT;
MODE LOOPINT = INT;
MODE POWMODSTRUCT = LINT;
PR READ "preclude/pow_mod.a68" PR;
PROC miller rabin = (LINT n, LOOPINT k)BOOL: (
IF n<=3 THEN TRUE
ELIF NOT ODD n THEN FALSE
ELSE
LINT d := n - 1;
INT s := 0;
WHILE NOT ODD d DO
d := d OVER 2;
s +:= 1
OD;
TO k DO
LINT a := 2 + ENTIER (random*(n-3));
LINT x := pow mod(a, d, n);
IF x /= 1 THEN
TO s DO
IF x = n-1 THEN done FI;
x := x*x %* n
OD;
else: IF x /= n-1 THEN return false FI;
done: EMPTY
FI
OD;
TRUE EXIT
return false: FALSE
FI
);
FOR i FROM 937 TO 1000 DO
IF miller rabin(i, 10) THEN
print((" ",whole(i,0)))
FI
OD</lang>
Sample output:
<pre>
937 941 947 953 967 971 977 983 991 997
</pre>
=={{header|Bc}}==
{{works with|GNU bc}}
| |||