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 { |g| 
		primes = []
		n = 2
		while 1 do
			prime = true
			for p in primes do
				if n%p == 0 then
					prime = false
			if prime then
				primes << n 
				g.yield n
			n += 1
g = prime_gen()
for i in 1..10000 do

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