Miller–Rabin primality test: Difference between revisions
Added 11l
(This is far accurate version in comparison to previous code, prev code were classifying prime as composite.) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 25:
* Deterministic variants of the test exist and can be implemented as extra (not mandatory to complete the task)
<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}}==
| |||