# 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

You’re currently reading “Euler problem 10,” an entry on blog

- Published:
- February 20, 2012 / 14:56

- Category:
- euler

- Tags:

## No comments yet

Jump to comment form | comment rss [?] | trackback uri [?]