Anonymous user
Factors of a Mersenne number: Difference between revisions
java < javascript
(→{{header|Pascal}}: add example) |
(java < javascript) |
||
Line 692:
13007</lang>
<lang j>trialfac 44497</lang>Empty output --> No factors found.
=={{header|Java}}==
Line 839 ⟶ 786:
M50 is not prime
M929 is not prime, has factor 13007
</pre>
=={{header|JavaScript}}==
<lang javascript>function mersenne_factor(p){
var limit, k, q
limit = Math.sqrt(Math.pow(2,p) - 1)
k = 1
while ((2*k*p - 1) < limit){
q = 2*k*p + 1
if (isPrime(q) && (q % 8 == 1 || q % 8 == 7) && trial_factor(2,p,q)){
return q // q is a factor of 2**p-1
}
k++
}
return null
}
function isPrime(value){
for (var i=2; i < value; i++){
if (value % i == 0){
return false
}
if (value % i != 0){
return true;
}
}
}
function trial_factor(base, exp, mod){
var square, bits
square = 1
bits = exp.toString(2).split('')
for (var i=0,ln=bits.length; i<ln; i++){
square = Math.pow(square, 2) * (bits[i] == 1 ? base : 1) % mod
}
return (square == 1)
}
function check_mersenne(p){
var f, result
console.log("M"+p+" = 2^"+p+"-1 is ")
f = mersenne_factor(p)
console.log(f == null ? "prime" : "composite with factor "+f)
}</lang>
<pre>
> check_mersenne(3)
"M3 = 2**3-1 is prime"
> check_mersenne(23)
"M23 = 2**23-1 is composite with factor 47"
> check_mersenne(929)
"M929 = 2**929-1 is composite with factor 13007"
</pre>
| |||