CODEWITHSUNDEEP
pythonalgorithmoptimizationprimes
11thHeaven
11thHeaven

Reputation: 379

Why does this make my prime-generating algorithm take longer?

I'm trying to find all primes below 1 000 000. As all non-primes can be factorised into primes, my method is to start my list of primes as [2, 3] and then run through every number up to 1 000 000. If a number is divisible by any number in prime_list, then it's not prime, and I move onto the next number. If this number isn't divisible by any number in prime_list, then it must be prime, and it gets added to this list.

To try and make this more efficient, I added a statement to only check if a number in question is divisible by values below the square root of this number. I thought this would cut out a lot of computation time but it actually makes my program take longer. Can anyone explain why?

Here's my code:

import math

import time
start_time = time.time()

prime = [2, 3]

def prime_checker(a):
    for j in prime:
        if j < (int(math.sqrt(a)) +1 ):     /// without this line, the program runs faster
            if a % j == 0:
                return False

for i in range (2, 100000):
    if prime_checker(i) != False:
        prime.append(i)

print prime[-1]

print "Time taken = ", time.time() - start_time

Upvotes: 1

Views: 142

Answers (5)

Andreikkaa
Andreikkaa

Reputation: 297

Your solution consumes O(N**1.5) time. To faster it, use Sieve of Eratosthenes. It's time complexity is O(NloglogN)).

n = 10 ** 5
sieve = [True] * n
sieve[0] = sieve[1] = False

for i in range(2, n):
    if sieve[i]:
        for j in range(i + i, n, i):
            sieve[j] = False

primes = []
for i, j in enumerate(sieve):
    if j:
        primes.append(i)

Upvotes: 0

dysfunctional
dysfunctional

Reputation: 131

Using **0.5 instead of math.sqrt also tends to be exponentially faster:

>>> import timeit
>>> print(timeit.timeit('math.sqrt(1830374)', setup='import math', number=10000))
0.0020401941434329274
>>> print(timeit.timeit('1830374**0.5', number=10000))
0.00015091430498159752

Chepner's code is the right answer though, just don't forget to iterate like rossum said. Iteration the way he stated will literally save you half a million calls (though, they will break quickly with Chepner's algorithm, that's still a lot of wasted time).

Upvotes: 0

chepner
chepner

Reputation: 531460

The time you spend repeatedly calculating the square root of a overwhelms whatever you save by skipping larger primes. Compute the square root once, which in my test is 10x faster than calculating it repeatedly (and about 3x faster than leaving the line out altogether).

def prime_checker(a):
    limit = int(math.sqrt(a)) + 1
    for j in prime:
        if j > limit:
            break
        if a % j == 0:
            return False
    return True

for i in range (2, 100000):
    if prime_checker(i):
        prime.append(i)

Upvotes: 2

Will Ness
Will Ness

Reputation: 71074

"If this number isn't divisible by any number in prime_list" that is not greater than this number's square root, then it is a prime.

And once you've hit a prime above the square root, all the rest of them will be so as well. We know this in advance.

The point is not to check whether to avoid each extraneous check, but to prevent all of them, in advance. This will speed up your code 100x, if not 1000x or even more.

In other words the real problem isn't the repeated calculation of the sqrt, but the incorrect handling of the limiting condition. With the correct handling of the limiting condition, even the repeated calculation of sqrt shouldn't matter much.

and the correct way is: break out from the loop as soon as possible, i.e. immediately when the first prime above the square root is reached; possibly by directly returning True right then and there.

Upvotes: 1

rossum
rossum

Reputation: 15685

To further speed up your algorithm, note that 2 is the only even prime. All other even numbers are composite. You already have prime = [2, 3] so you can start searching at 5 (4 is not prime) and only check odd numbers:

for i in range (5, 100000, 2):
    if prime_checker(i) != False:
        prime.append(i)

Upvotes: 3

Related Questions