Factors of a Mersenne number: Difference between revisions
Added Wren
m (Rust - reformatted with rustfmt) |
(Added Wren) |
||
Line 3,341:
<pre>
M47 factor=2351
</pre>
=={{header|Wren}}==
{{trans|JavaScript}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<lang ecmascript>import "/math" for Int
import "/fmt" for Conv, Fmt
var trialFactor = Fn.new { |base, exp, mod|
var square = 1
var bits = Conv.itoa(exp, 2).toList
var ln = bits.count
for (i in 0...ln) {
square = square * square * (bits[i] == "1" ? base : 1) % mod
}
return square == 1
}
var mersenneFactor = Fn.new { |p|
var limit = (2.pow(p) - 1).sqrt.floor
var k = 1
while ((2*k*p - 1) < limit) {
var q = 2*k*p + 1
if (Int.isPrime(q) && (q%8 == 1 || q%8 == 7) && trialFactor.call(2, p, q)) {
return q // q is a factor of 2^p - 1
}
k = k + 1
}
return null
}
var m = [3, 5, 11, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 67, 71, 73, 79, 83, 97, 929]
for (p in m) {
var f = mersenneFactor.call(p)
Fmt.write("2^$3d - 1 is ", p)
if (f) {
Fmt.print("composite (factor $d)", f)
} else {
System.print("prime")
}
}</lang>
{{out}}
<pre>
2^ 3 - 1 is prime
2^ 5 - 1 is prime
2^ 11 - 1 is composite (factor 23)
2^ 17 - 1 is prime
2^ 23 - 1 is composite (factor 47)
2^ 29 - 1 is composite (factor 233)
2^ 31 - 1 is prime
2^ 37 - 1 is composite (factor 223)
2^ 41 - 1 is composite (factor 13367)
2^ 43 - 1 is composite (factor 431)
2^ 47 - 1 is composite (factor 2351)
2^ 53 - 1 is composite (factor 6361)
2^ 59 - 1 is composite (factor 179951)
2^ 67 - 1 is composite (factor 193707721)
2^ 71 - 1 is composite (factor 228479)
2^ 73 - 1 is composite (factor 439)
2^ 79 - 1 is composite (factor 2687)
2^ 83 - 1 is composite (factor 167)
2^ 97 - 1 is composite (factor 11447)
2^929 - 1 is composite (factor 13007)
</pre>
| |||