Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(Python added (from bc)) |
|||
Line 21: | Line 21: | ||
* Deterministic variants of the test exist and can be implemented as extra (not mandatory to complete the task) |
* 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}}== |
=={{header|Bc}}== |
||
{{works with|GNU bc}} |
{{works with|GNU bc}} |