Prime Number Generator Optimisation (Project Euler #7)

Question

I want to optimize this code so that the time to complete this task is shorter (I do want to keep printing all the prime numbers along the way):

(Getting 10001st prime number)

counter = 10001
target_num = 1          #because if we add 1 to it the first time, it will become 2
input('This may take a while, press Enter to continue; you can stop the program any time by pressing CTRL + C.')
while counter <= 10001 and counter > 0:
    target_num = target_num + 1
    for x in range(1, target_num + 1):
        if target_num % x == 0:
            if x == 1:
                pass
            elif x != target_num:
                break
            elif x == target_num:
                counter = counter - 1
                print (target_num)  #prints prime number so user knows if program is actually crunching numbers
print ('10001st prime number is: ' + str(target_num))

Look into sieve of Eratosthenes to calculate prime numbers faster. Your algorithm is currently extremely inefficient. One quick hack to save time would be to skip checking any even number because we know that they are all non-prime save for 2. The slowness of your code here is mostly due to bad algorithm rather than bad Python I suspect. — ApplePie, Jul 09 '17 at 03:37
you can just check until floor(sqrt(target_num))+1, because of the fact that if a< sqrt(x), then a*sqrt(x) — Park, Jul 09 '17 at 03:38
@minitotent Python 3, my code is very inefficient as others have mentioned already. — 선풍기, Jul 09 '17 at 04:34
@선풍기 Are you looking for any further clarification from my answer? — cs95, Jul 09 '17 at 05:14
@cᴏʟᴅsᴘᴇᴇᴅ it was a fantastic answer, thank you! — 선풍기, Jul 10 '17 at 05:21

cs95 · Accepted Answer · 2017-07-09T03:57:45.547

I timed your code. This is how long it takes:

Over 72 seconds (%timeit died, sorry!)

The glaring issue is the fact that you run your loop from 1 to target_num to find primes. That's not necessary.

Proof of that can be seen here.

Here's a version that runs upto the square root. You can remove those redundant ifs too.

def foo():
    counter = 10001
    target_num = 1          #because if we add 1 to it the first time, it will become 2
    while counter <= 10001 and counter > 0:
        target_num = target_num + 1
        for x in range(2, int(target_num ** 0.5) + 1 ):
            if target_num % x == 0:
                if x != target_num:
                    break
        else:
            counter -= 1

    print ('10001st prime number is: ' + str(target_num))

Timing:

1 loop, best of 3: 442 ms per loop

Further speedups may be achieved by stepping range by 2, so you skip checks for even numbers:

def foo():
    counter = 10000
    target_num = 1          
    while counter <= 10001 and counter > 0:
        target_num = target_num + 2
        ...

Timing:

1 loop, best of 3: 378 ms per loop

Footnote: This answer explains the inadequacies of your current approach. However, for a completely new approach, check out Sieve of Eratosthenes - Finding Primes Python, or @AChampion's answer.

AChampion · Answer 2 · 2017-07-09T04:25:17.793

There a many resources for fast prime number generators.
For example, you could install primesieve which provides:

In []:
import primesieve
primesieve.nth_prime(10001)

Out[]:
104743

In []:
%timeit primesieve.nth_prime(10001)

Out[]:
28.3 µs ± 549 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

A native python implementation of a simple sieve:

In []:
import itertools as it

def primes():
    yield 2
    sieve = {}
    for n in it.count(3, 2):
        if n not in sieve:
            sieve[n*n] = 2*n
            yield n
            continue
        a = sieve.pop(n)
        x = n + a
        while x in sieve:
            x += a
        sieve[x] = a

def nth_prime(n):
    return next(it.islice(primes(), n-1, None))

nth_prime(10001)

Out[]:
104743

In []:
%timeit nth_prime(10001)

Out[]:
26.3 ms ± 629 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Prime Number Generator Optimisation (Project Euler #7)

2 Answers2