I’ve been getting into Project Euler a little bit more recently. I found this puzzle really interesting:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^{th} prime is 13.

What is the 10001^{st} prime number?

#### My Original Solver

To my knowledge, there isn’t anyway of telling if a number is prime except from dividing it by all the numbers between 1 and the number and seeing if they are factors. So I implemented the following in Python:

# Python Script to find 1001th prime number

# Original Method

import datetime

start = datetime.datetime.utcnow()

print '\nOriginal Method'

i = 0

n = 1

while i < 1001:

n = n + 1

fail = 0

for j in range(2,n):

if n % j == 0:

fail = 1

if fail == 0:

i = i + 1

#print str(i) + '. ' + str(n)

if i == 1001:

print 'The 1001st prime number is ' + str(n)

print 'Time Taken: '+str(datetime.datetime.utcnow() - start)

Note the script above calculates the 1001st prime rather than the 10001st prime as the challenge states. When I used a similar script to find the 10,001st prime it took quite a long time on my computer so using the 1,001st to benchmark makes it a lot easier.

Unscientific testing gives the following output after 3 runs (around 21 seconds to solve):

Original Method

The 1001st prime number is 7927

Time Taken: 0:00:18.344000

Original Method

The 1001st prime number is 7927

Time Taken: 0:00:21.047000

Original Method

The 1001st prime number is 7927

Time Taken: 0:00:25.078000

#### Stopping

I noticed in the above code that even when the script finds a factor of a number, it’d still continue searching every number above that to see if they were factors. I put in a check:

for j in range(2,n):

**if fail == 0:**

if n % j == 0:

fail = 1

This gave the following output after 3 runs:

Original Method + Factor Stop

The 1001st prime number is 7927

Time Taken: 0:00:09.547000

Original Method + Factor Stop

The 1001st prime number is 7927

Time Taken: 0:00:11.813000

Original Method + Factor Stop

The 1001st prime number is 7927

Time Taken: 0:00:13.750000

This halved the time it took to find the 1001st prime number.

#### Square Roots

With the remaining prime numbers, the script was still searching every single number between 1 and that number in order to determine whether it was a factor. For example with 13, there is no point in checking whether 8, 9, 10, 11 or 12 are factors because they would have to be multiplied by a number between 1 and 2 to get 13 and obviously there are no integers between 1 and 2.

After thinking about it, I realised that there was no point in searching any of the numbers greater than the square root of the number. With the number 12, this means you only have to search up to 3.46 (ceil to 4). Sure, 6 is a factor but you need to multiply it by 2 to make 12. Any factor above the square root of the number will have to be multiplied by a factor smaller than the square root to make the number.

I changed the script so it’d only search numbers up to the square root:

n = n + 1

fail = 0

for j in range(2,**(n**0.5)+1**):

if fail == 0:

This had a drastic effect on the time required:

Stop at square root method

The 1001st prime number is 7927

Time Taken: 0:00:00.313000

Stop at square root method

The 1001st prime number is 7927

Time Taken: 0:00:00.516000

Stop at square root method

The 1001st prime number is 7927

Time Taken: 0:00:00.453000

From 21 seconds to 0.4 seconds – a speed up of 5000%.

The square root method managed to calculate the 10,001st prime in 11 seconds – a far cry from the 20 minutes or so required using the original script.