#### Description

From Project Euler: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 10001st prime number?

#### Solution

Finding primes is an interesting problem. There are a number of ways that we can go about doing so, and it is something we will need to do several times throughout the Project Euler problems. So we will want to develop a solution that is not only accurate, but also fairly efficient.A fairly efficient method for finding all of the prime numbers below a given value is the Sieve of Eratosthenes. The way it works is simple:

- Create a list of consecutive integers from two to n: (2, 3, 4, …,
*n*) - Start with
*p*= 2, the first prime number. - Remove from the list all multiples of
*p*less than or equal to*n*. - Find the smallest number remaining on the list greater than
*p*. This is the next prime number. Set*p*equal to this number. - Repeat this process until
*p*is greater than^{2}*n*. - All remaining numbers on the list are prime.

- If we want an arbitrary limit, there is no
*n*value, so we cannot stop striking composite numbers as in step 5 above. - Since we have no upper bound, striking all of the multiples of
*p*would be impossible (there are infinitely many). So we will only strike the next multiple and worry about the larger ones when we get to them. - There is insufficient memory to store a list of all numbers (obviously), so we will ignore all primes that have already been yielded and all composites that have already been stricken. Thus we will only store a list of composites that will need to be stricken when we reach them.

One final note before we start implementing our algorithm. When we reach a prime number

*p*, we do not need to strike the first

*p-1*multiples of

*p.*This is because those multiples will be a multiple of another prime as well. This can easily be seen with an example:

- Given the prime number
*p*= 11 - 2
*p*= 22 which is a multiple of 2 - 3
*p*= 33 which is a multiple of 3 - 4
*p*= 2*2*p*= 44 which is a multiple of 2 - 5
*p*= 55 which is a multiple of 5 - 6
*p*= 2*3*p*= 66 which is a multiple of both 2 and 3 - 7
*p*= 77 which is a multiple of 7 - 8
*p*= 2*2*2*p*= 88 which is a multiple of 2 - 9
*p*= 3*3*p*= 99which is a multiple of 3 - 10
*p*= 5*2*p*= 110 which is a multiple of both 2 and 5 - 11
*p*= 121 which is only a multiple of 11.

*p*, the first composite we need to concern ourselves with is

*p*.

^{2}class PrimeGenerator include Enumerable def each composites = {} n = 2 while true if composites.has_key?(n) factors = composites.delete(n) factors.each { |factor| composites.merge!(n + factor => [factor]) { |key,left,right| left + right } } else composites.merge!(n**2 => [n]) { |key,left,right| left + right } yield n end n += 1 end end end

PrimeGenerator.new.take(10001).drop(10000).first

## No comments:

Post a Comment