Project Euler Problem #7 in Python (10001st prime number)

Question

I have managed to solve the 7th Project Euler problem, however I think it can be improved by a lot, I am by no means a professional programmer or even consider myself really good at it. Any improvements / suggestions would be really helpful.

Problem statement:

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?

This is my solution.

counter = 2
n = 10001
for i in range(3, 1000000, 2):
 k = 1
 while k < i:
  k += 2
  if i % k == 0:
   break
  if k + 2 == i:
   counter += 1
  if counter == n:
   print(i)
   raise ZeroDivisionError

The program does skip 2 and 3, in an attempt of mine to make it faster. At the end I raise an error in order to stop the program from looping.

Answer 1

Upper bound for p_n

There is a known upper bound for the n-th prime.

It means that you don't need to guess how large it could be. upper_bound_for_p_n(10001) tells us in less than a micro-second that the desired number cannot be larger than 114320.

You just need to apply the Sieve of Erathosthenes up to 114320 and you're done:

from math import log, ceil

def find_primes(limit):
    nums = [True] * (limit + 1)
    nums[0] = nums[1] = False

    for (i, is_prime) in enumerate(nums):
        if is_prime:
            yield i
            for n in range(i * i, limit + 1, i):
                nums[n] = False

def upper_bound_for_p_n(n):
    if n < 6:
        return 100
    return ceil(n * (log(n) + log(log(n))))

def find_n_prime(n):
    primes = list(find_primes(upper_bound_for_p_n(n)))
    return primes[n - 1]

It calculates the 10001th prime in 15ms on my computer, compared to 35s for your code.

Answer 2

I'm not going to pay attention to your algorithm, as Arnav is right there, but instead focus on style problems. It should be a giant red flag when you raise a ZeroDivisionError when you aren't dividing by zero. The correct solution here is to put your code inside a function, which will let you return the correct result. While here, you might as well make the upper limit of your range n*n instead of 1,000,000, which will let it work for bigger values. Also, I know I said I wouldn't focus on the algorithm, but you can make the inner loop be while k*k<i, as any prime factor of n will be less than the n**.5. This simple change makes your code take .1 second instead of 30.

def nth_prime(n):
    counter = 2
    for i in range(3, n**2, 2):
        k = 1
        while k*k < i:
            k += 2
            if i % k == 0:
               break
        else:
            counter += 1
        if counter == n:
            return i

print(nth_prime(100001))

Answer 3

What I dislike about your solution is the unnecessarily large amount of complexity your code has, which takes a toll on its performance.

When I solved this problem myself, I used the Sieve of Eratosthenes to generate a list of prime numbers up to an arbitrary limit (I also picked one million, but you could use a formula to compute it) and indexed that list at 10,000 to get the 10,001st number.

Here is how I implemented the sieve:

def primes_upto(limit):
    limitN = limit+1
    not_prime = set()
    primes = [2]

    for i in range(3, limitN, 2):
        if i in not_prime:
            continue

        for j in range(i*3, limitN, i*2):
            not_prime.add(j)

        primes.append(i)
    return primes

As you can see, this approach reduces the complexity of your code. Also, this is approximately 28 seconds quicker than your approach.

Answer 4

One way to solve this problem and use memory efficiently is through generators, this way only one prime at the time is processed and you won't get out of memory

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n < 2:
        return False
    limit = int(n ** 0.5) + 1
    for i in range(3, limit, 2):
        if n % i == 0:
            return False
    return True

def next_prime(count_limit):
    yield 2
    count = 1
    n = 3
    while True:
        if is_prime(n):
            yield n
            count += 1
            if count == count_limit:
                return
        n += 2

n = 10001

# Good
item = None
for item in next_prime(n):
    pass
print(item)

# Better
from collections import deque
dd = deque(next_prime(n), maxlen=1)
print(dd.pop())

Aditionally, if you need to run it several times, memoizing is suggested:

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def is_prime(n):
    ...