Factors of a Mersenne number: Difference between revisions

Content added Content deleted
m (→‎{{header|Perl}}: wrong output)
(Updated D code)
Line 364: Line 364:


=={{header|D}}==
=={{header|D}}==
<lang d>import std.stdio, std.math;
<lang d>import std.stdio, std.math, std.traits;


ulong mersenneFactor(ulong p) {
ulong mersenneFactor(in ulong p) pure nothrow {
ulong limit = cast(ulong) sqrt(2 ^^ p - 1);
static bool isPrime(T)(in T n) pure nothrow {
for (ulong k = 1; 2 * p * k - 1 < limit; k++) {
if (n < 2 || n % 2 == 0)
ulong q = 2 * p * k + 1;
return n == 2;
if (isPrime(q) && (q % 8 == 1 || q % 8 == 7) && modpow(2, p, q) == 1) {
for (Unqual!T i = 3; i ^^ 2 <= n; i += 2)
return q;
if (n % i == 0)
}
return false;
⚫
return true;
}
}
⚫
return 0;
}


long modpow(long b, long e, long m) {
static long modPow(in long cb,in long ce,in long m) pure nothrow{
long result = 1;
long b = cb;
while (e > 0) {
long result = 1;
if ((e & 1) == 1) {
for (long e = ce; e > 0; e >>= 1) {
result = (result * b) % m;
if ((e & 1) == 1)
result = (result * b) % m;
b = (b ^^ 2) % m;
}
}
b = (b * b) % m;
return result;
e >>= 1;
}
}
return result;
}


immutable ulong limit = cast(ulong)sqrt(2 ^^ p - 1);
bool isPrime(T) (T n) {
if (n < 2 || n % 2 == 0) return n == 2;
for (ulong k = 1; (2 * p * k - 1) < limit; k++) {
for (T i = 3 ; i * i <= n ; i += 2) {
immutable ulong q = 2 * p * k + 1;
if (n % i == 0) {
if (isPrime(q) && (q % 8 == 1 || q % 8 == 7) &&
return false;
modPow(2, p, q) == 1)
}
return q;
}
}
return true;
return 0;
}
}


Line 402: Line 400:
writefln("Factor of M929: %s", mersenneFactor(929));
writefln("Factor of M929: %s", mersenneFactor(929));
}</lang>
}</lang>
Output:
<pre>Factor of M929: 13007</pre>


=={{header|Forth}}==
=={{header|Forth}}==
Retrieved from "https://rosettacode.org/wiki/Factors_of_a_Mersenne_number"