9
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Also, 1.26*n*log(n) is a tighter upper bound for n>17 \$\endgroup\$ – Oscar Smith Feb 22 '18 at 20:08
3
\$\begingroup\$

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice. It's still pretty close to OP's code while not being too inefficient. You need print(nth_prime(10001)), though. \$\endgroup\$ – Eric Duminil Feb 22 '18 at 10:31
3
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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):
    ...
\$\endgroup\$
  • \$\begingroup\$ The first half of this isn't so much a review as an alternate method. You talk about reducing memory, but OP's algo was already O(1) \$\endgroup\$ – Oscar Smith Feb 22 '18 at 3:23
  • \$\begingroup\$ You could also use islice to access the n-th element of your generator. You could also rename your functions. I wouldn't expect next_prime to return a generator of primes. \$\endgroup\$ – Eric Duminil Feb 22 '18 at 10:32

protected by Community Dec 15 '18 at 3:01

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.