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.

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))

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.

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.

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):

    ...

I use generator also.

def prime():





  import itertools





  yield 2



  for i in itertools.count(3, 2):

    if i == 2:

      yield 2

    else:

      e = int(i**.5) + 1

      for j in range(2, e+1):

        if  i % j == 0:

          break

        elif j < e:

          continue

        else:

          yield i



for i, n in enumerate(prime()):

  if i < 10001:

    pass

  elif i == 10001:

    print(n)

  else:

    break