What is the largest prime factor of the number 600851475143 ?
-----
I wrote this piece of disgusting, un-Rubylike Ruby to get the answer by creating a list of a number's prime factors:
def factor(composite)
i=1
flag=false
primefactors =[]
while (i < composite)
i=i+1
primefactors.each{|p| flag=true if (i%p).zero?}
if flag then flag=false
else # if it is a prime
primefactors.push(i) #add the prime (since it's a prime factor)
while (composite%i).zero? # as long as n is divisbible by the prime
composite /= i # divide n by the prime
end
end
end
primefactors
end
puts factor(600851475143).last
And then I learned that ruby has a prime number generator. All I need to do is:
require 'mathn'
n = 600851475143
factor = 0
primes = Prime.new
while n > 1
factor = primes.next
while (n % factor).zero?
n /= factor
end
end
puts factor
I am slightly ashamed.