I couldn’t decide what to do, so I thought it was time to solve more random hard problems.
This is the seventh post in my Project Euler series. The sixth problem is here.
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?
It’s probably pretty clear that with us looking for so many large prime numbers, we’ll probably need to use a BigInteger library. Because of that, I’m going to use Ruby. Numbers in Ruby are Fixnum, but when they get large enough, they automatically become Bignum (documentation). Objective-C’s unsigned long long might do the trick, but Ruby’s way is just more friendly to a problem like this.
The obvious way to solve the problem is to just start generating prime numbers. Once we have generated 10,001 prime number’s we’re done.
The brute force method of determining if a number is prime would work just fine. For a number, try dividing it by all numbers up to the square root of itself. But this method is a bit slow. I’m using these problems as a way to learn more, so it makes sense to do some thinking and optimize things.
The fastest algorithm I can memorize and keep straight in my mind is the Sieve of Eratosthenes.
The Sieve of Eratosthenes is pretty easy to understand.
- Make a list of numbers 2 through n
- Take the first number from the list, it is prime.
- Remove all multiples of this number from the list
- Move to the next number in the list, it is prime. Go back to step 3.
The only downside to using this algorithm is that the largest prime number you can find is determined by the length of your list.
Because of this limitation, it would make perfect sense for a “Find all prime numbers less than x” problem, but not so much for a “Find the first x prime numbers”. Solving this problem with the Sieve of Eratosthenes is a wicked problem, we must first solve it to be able to solve it. We could guess and check until we solved the problem, but that just doesn’t seem like a good answer to me.
But knowing the Sieve of Eratosthenes, we can do some clever thinking.
The brute force method works by taking a number and testing to see if it is prime. The Sieve of Eratosthenes works by removing non-prime numbers from a list. Working opposite from each other. However, we can use the Sieve of Eratosthenes to make a big optimization to the brute force method.
With the Sieve of Eratosthenes, we eliminate numbers from being prime based only on other prime numbers. The number 20 was eliminated when we removed multiples of 2. The number 21 was eliminated when we removed multiples of 3. This is because all numbers are divisible by 1 or more prime, and the number 1. If the number is only divisible by 1 prime, it is divisible only by itself, and is therefore prime.
So with all that in mind, we will FINALLY solve the problem. We will increment a counter, and if it is prime, we will put it in an array. To test to see if a number is prime, we will compare it to the other numbers in the array.
This method is not as fast as the Sieve of Eratosthenes, but its a simple enough algorithm to memorize. But if you want to do something really hard, go look up the Sieve of Atkin.
I decided to use Ruby to solve this problem because it automatically switches to start using Bignum if your numbers get large enough. After solving the problem i discovered that the answer doesn’t get large enough to even worry about that. But I really liked how pretty the answer looks in Ruby
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#! /usr/bin/env ruby $primes = [2, 3, 5, 7] nth = 10001 def is_prime? number $primes.each do |p| return true if p * p > number return false if number % p == 0 end true end count = 11 while $primes.length < nth do $primes << count if is_prime? count count+=1 end puts $primes[nth - 1] |