Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(This is far accurate version in comparison to previous code, prev code were classifying prime as composite.) |
Alextretyak (talk | contribs) (Added 11l) |
||
| Line 25: | Line 25: | ||
* 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) |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|D}} |
|||
<lang 11l>F isProbablePrime(n, k = 10) |
|||
I n < 2 | n % 2 == 0 |
|||
R n == 2 |
|||
V d = n - 1 |
|||
V s = 0 |
|||
L d % 2 == 0 |
|||
d I/= 2 |
|||
s++ |
|||
assert(2 ^ s * d == n - 1) |
|||
L 0 .< k |
|||
V a = random:(2 .< n) |
|||
V x = pow(a, d, n) |
|||
I x == 1 | x == n - 1 |
|||
L.continue |
|||
L 0 .< s - 1 |
|||
x = pow(x, 2, n) |
|||
I x == 1 |
|||
R 0B |
|||
I x == n - 1 |
|||
L.break |
|||
L.was_no_break |
|||
R 0B |
|||
R 1B |
|||
print((2..29).filter(x -> isProbablePrime(x)))</lang> |
|||
{{out}} |
|||
<pre> |
|||
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||