Euler Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

We can solve this reasonably quickly using a very basic algorithm for generating primes:
– 2 is prime
– a number is prime if it can’t be divided by any prime less than it
– so generate primes by looping and testing for divisibility against prime list

Code looks something like this:

require 'generator'
def prime_gen()
	return  Generator.new { |g| 
		primes = []
		n = 2
		while 1 do
			prime = true
			for p in primes do
				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()
 
for i in 1..10000 do
	g.next
end
puts g.next

While this code is fast enough for problem 7, this is not the last time we’ll see a problem requiring prime number generation; we’ll discuss optimizations in a later post.


About this entry