Anonymous user
Miller–Rabin primality test: Difference between revisions
Improved D entry
m (whitespace/{{out}}) |
(Improved D entry) |
||
Line 536:
<lang d>import std.random;
bool isProbablePrime(in ulong n, in int k) {
pure nothrow {
long result = 1;▼
while (e > 0) {▼
if ((e & 1) == 1) {▼
result = (result * b) % m;▼
}▼
b = (b * b) % m;▼
e >>= 1;▼
}▼
return result;▼
}
if (n < 2 || n % 2 == 0)
return n == 2;
Line 551 ⟶ 564:
foreach (_; 0 .. k) {
ulong a = uniform(2, n);
ulong x =
if (x == 1 || x == n - 1)
continue;
foreach (__; 1 .. s) {
x =
if (x == 1) return false;
if (x == n - 1) continue outer;
Line 565 ⟶ 578:
}
void main() { // demo code
▲pure nothrow long modpow(long b, long e, long m) {
import std.stdio, std.range, std.algorithm;
▲ long result = 1;
writeln(filter!(n => isProbablePrime(n, 10))(iota(2, 30)));
▲ while (e > 0) {
▲ if ((e & 1) == 1) {
▲ result = (result * b) % m;
▲ }
▲ b = (b * b) % m;
▲ e >>= 1;
▲ }
▲ return result;
}</lang>
{{out}}
<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]</pre>
=={{header|E}}==
| |||