Euler Project Problem #003

euler3.rb

# Solution to Project Euler's third problem
# http://projecteuler.net/index.php?section=problems&id=3
# What is the largest prime factor of the number 600851475143?
def generate_primes(ceiling)
	primes, count = [1, 2], 1
	until primes.last > Math.sqrt(ceiling) do
		numbers = (primes[count-1]**2+1..primes[count]**2).to_a
		1.upto(count) {|c| numbers.select! {|number| number%primes[c] != 0}}
		primes.concat(numbers)
		count += 1
	end
	primes.shift #remove 1
	return primes
end
def factor(number, primes)
	factors = []
	until Math.sqrt(number) < primes.first
		p = primes.shift
		if number % p == 0 then 
			factors.push p
			number = number / p
			primes.unshift p
		end
	end
	factors.push number
	return factors
end
number = 600_851_475_143
primes = generate_primes(number)
factors = factor(number, primes)
p factors