Euler problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

It’s time for prime generation round 2! Our previous method in problem 7 was kinda slow, and can’t make it to 2,000,000. But one simple optimization saves more than half the time. Since no prime factor of a number n can be larger than the quare root of n, once we’ve tried dividing by all primes less than or equal to sqrt(n), we know we have a prime.

require 'generator'
 
def prime_gen()
	return  Generator.new { |g| 
		primes = []
		n = 2
		while 1 do
			root = Math.sqrt(n).to_i + 1
			prime = true
			for p in primes do
				break if p > root
				if n%p == 0  then
					prime = false
					break
				end
			end
			if prime then
				primes << n 
				g.yield n
			end
			n += 1
		end
	}
end
 
g = prime_gen()
n = 0
sum = 0
while n < 2000000 do
	sum += n
	n = g.next
end
puts sum

This is still a somewhat slow process, but it does get us our answer in a reasonable amount of time. There’s still many more approaches we can try to speed things up though, which we may need to employ for the next big prime generation question.


About this entry