14 lines
447 B
Ruby
14 lines
447 B
Ruby
# Get prime decomposition of integer _i_.
|
|
# This routine is terribly inefficient, but elegance rules.
|
|
def prime_factors(i)
|
|
v = (2..i-1).detect{|j| i % j == 0}
|
|
v ? ([v] + prime_factors(i/v)) : [i]
|
|
end
|
|
|
|
# Example: Decompose all possible Mersenne primes up to 2**31-1.
|
|
# This may take several minutes to show that 2**31-1 is prime.
|
|
(2..31).each do |i|
|
|
factors = prime_factors(2**i-1)
|
|
puts "2**#{i}-1 = #{2**i-1} = #{factors.join(' * ')}"
|
|
end
|