0x0008 - Project Euler 007

Problem:

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?

Solution:

1. Brute-force approach:

from math import sqrt
def is_prime(n) :
    for i in range(2, int(sqrt(n)+1)) :
        if n % i == 0:
            return False
    return True

limit, count, num = 10001, 1, 1
while count < limit:
    num += 2
    if is_prime(num) : count += 1
print num

2. Efficient approach:

from math import sqrt
def is_prime(n) :
    if n == 2 or n == 3: return True
    if n < 2 or n % 2 == 0: return False
    if n % 3 == 0: return False
    if n < 9: return True

    r, f = int(sqrt(n)), 5
    while f <= r:
        if n % f == 0 or n % (f + 2) == 0: return False
        f += 6
    return True

limit, count, num = 10001, 1, 1
while count < limit:
    num += 2
    if is_prime(num) : count += 1
print num

Analysis:

The isprime() methods in the brute-force and efficient approaches are respectively Methods 1 and 5 from the previous post on Primality Testing. The remaining part of the code is the same for both approaches.

• The variable limit holds the nth prime number to be found.
• count stores the number of prime numbers found until now.
• num is the current number to be checked for primality.

As long as count is less than limit, num is checked for primality. Within the while loop, n is always incremented by 2 as we need only test odd numbers. Every time a prime number is encountered, i.e. num is found to be prime, count is incremented once. The terminating condition of the while loop occurs when count equals limit. In other words, we have found limit prime numbers. So, breaking out of the loop, we print the value of num, which is the last prime number found.

Running time:

Using Python 2.7 under Ubuntu 10.10 terminal the following running times were clocked:

Brute-force approach: 325.934 milliseconds

Efficient approach: 170.864 milliseconds (52.42% of the time)