Problem #7 is one of the many problems on Project Euler which concerns prime numbers. The question reads:
Project Euler Problem 7: 10001st prime
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?
As discussed in my post for Problem #3, an easy way to check if a number n is prime is to check if any numbers between 2 and the square root of n are divisors of n. Using this fact, we can do the following simple brute force approach to solve this problem:
Solution #1: The Brute Force Approach
We simply check every integer starting at 2 and going up while keeping count of the number of primes that have been encountered. Once the 10,001st prime number is encountered, the program is complete. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #7
'''
import time
from math import sqrt
def isPrime(n):
c = 2
while(c<=sqrt(n)):
if(n%c==0):
return False
c+=1
return True
def projectEulerProblemSeven(n):
total = 0
c = 2
while(total<n):
if(isPrime(c)):
total+=1
c+=1
return c-1
start = time.time()
print projectEulerProblemSeven(10001)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
104743
--- 0.310272932053 seconds ---
for input of n = 10001
'''
As shown above, this approach is quite decent. However, with some more complex math, we can solve this problem with another approach:
Solution #2: Sieve of Eratosthenes Approach
A well known method for compiling a list of all of the primes up to a certain point is the Sieve of Eratosthenes. This method involves listing all of the numbers up to a point and then working up the number line, crossing off any multiples of the earliest number which has not been crossed off. As it turns out, this method can be used to make this algorithm more efficient. The one problem is that the question is asking for the 10,001st prime, not the number of primes less than 10,001.
As it turns out, some upper bounds for the nth prime are known. The Prime Number Theorem tells us that the nth prime is less than or equal to n*(ln(n)+ln(ln(n))). The proof for this fact is far beyond my mathematical expertise, so I have left a link for this fact if you wish to read more about it. Using this upper bound, we can use the Sieve of Eratosthenes to list all primes up to the upper bound for the 10,001st prime and then read the 10,001st prime off the list. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #7
'''
import time
from math import log
def sieveEratosthenes(n):
myPrimes = []
primePossible = [True]*(n+1)
primePossible[0] = False
primePossible[1] = False
for (i,possible) in enumerate(primePossible):
if(possible):
for x in range(i*i, n+1, i):
primePossible[x] = False
myPrimes.append(i)
return myPrimes
def projectEulerProblemSeven(n):
if(n==1):
return 2
elif(n==2):
return 3
elif(n==3):
return 5
pntLimit = int(n*(log(n)+log(log(n))))
allPossible = sieveEratosthenes(pntLimit)
return allPossible[n-1]
start = time.time()
print projectEulerProblemSeven(10001)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
104743
--- 0.0170910358429 seconds ---
for input of n = 10001
'''
As shown above, this approach is much more efficient with a decent implementation of the Sieve of Eratosthenes. Once again, knowing some higher level math can really make the solutions for these problems more efficient.
This marks one complete week of Project Euler problems and over 1% completion of all the problems. Hooray! Thank you for reading.
The Inner Machinations of Walker 