Anonymous user
Miller–Rabin primality test: Difference between revisions
Updated D entry
(Added a much more readable, simpler and faster algorithm.) |
(Updated D entry) |
||
Line 840:
<lang d>import std.random;
bool isProbablePrime(in ulong n, in
static
pure nothrow @safe @nogc {
while (e > 0) {
if ((e & 1) == 1)
result = (result * b) % m;
b = (b * b) % m;▼
e >>= 1;
}
Line 854 ⟶ 853:
}
if (n < 2 || n % 2 == 0)
return n == 2;
Line 863 ⟶ 862:
s++;
}
assert(2 ^^ s * d == n - 1);
outer:
foreach (immutable _; 0 .. k) {
immutable ulong a = uniform(2, n);
ulong x = modPow(a, d, n);
if (x == 1 || x == n - 1)
continue;
foreach (immutable __; 1 .. s) {
x = modPow(x, 2, n);
if (x == 1)
continue outer;
}
return false;
Line 882 ⟶ 883:
}
void main() { //
import std.stdio, std.range, std.algorithm;
iota(2, 30).filter!isProbablePrime.writeln;
}</lang>
{{out}}
| |||