Anonymous user
Factors of a Mersenne number: Difference between revisions
no edit summary
m (Put Sieve of Eratosthenes implementation in separate header file) |
No edit summary |
||
Line 853:
M53 = 2**53-1 is composite with factor 6361.
M929 = 2**929-1 is composite with factor 13007.</pre>
=={{header|Crystal}}==
<lang ruby>require "big"
def prime?(n) # P3 Prime Generator primality test
return n | 1 == 3 if n < 5 # n: 0,1,4|false, 2,3|true
return false if n.gcd(6) != 1 # for n a P3 prime candidate (pc)
pc1, pc2 = -1, 1 # use P3's prime candidates sequence
until (pc1 += 6) > Math.sqrt(n).to_i # pcs are only 1/3 of all integers
return false if n % pc1 == 0 || n % (pc2 += 6) == 0 # if n is composite
end
true
end
# Compute b**e mod m
def powmod(b, e, m)
r, b = 1.to_big_i, b.to_big_i
while e > 0
r = (r * b) % m if e.odd?
b = (b * b) % m
e >>= 1
end
r
end
def mersenne_factor(p)
mp_num = 2.to_big_i ** p - 1
k = 1.to_big_i
while (k * 2 * p - 1) ** 2 < mp_num
q = k * 2 * p + 1
if prime?(q) && (q % 8 == 1 || q % 8 == 7) && (powmod(2, p, q) == 1)
# q is a factor of 2**p-1
return q
end
k += 1
end
true # could also set to `0` value to check for
end
def check_mersenne(p)
print "M#{p} = 2**#{p}-1 is "
f = mersenne_factor(p)
(puts "prime"; return) if f.is_a?(Bool) # or f == 0
puts "composite with factor #{f}"
end
(2..53).each { |p| check_mersenne(p) if prime?(p) }
check_mersenne 929</lang>
{{out}}
<pre>M2 = 2**2-1 is prime
M3 = 2**3-1 is prime
M5 = 2**5-1 is prime
M7 = 2**7-1 is prime
M11 = 2**11-1 is composite with factor 23
M13 = 2**13-1 is prime
M17 = 2**17-1 is prime
M19 = 2**19-1 is prime
M23 = 2**23-1 is composite with factor 47
M29 = 2**29-1 is composite with factor 233
M31 = 2**31-1 is prime
M37 = 2**37-1 is composite with factor 223
M41 = 2**41-1 is composite with factor 13367
M43 = 2**43-1 is composite with factor 431
M47 = 2**47-1 is composite with factor 2351
M53 = 2**53-1 is composite with factor 6361
M929 = 2**929-1 is composite with factor 13007</pre>
=={{header|D}}==
| |||