Why this sieve method of finding primes is slower than a brute force

Question

Newbie to python trying to learn with a Prime Finding program here!

I know this is a common question and from my research I know there's a couple optimizations I could make: 1) Preallocate a fixed array of booleans so no resizing needs to take place 2) Use primitives rather than objects

However, I still don't understand why this sieve is SO much slower, any thoughts? Both use appending to lists and iterating over them. My intuition was the sieve would just have to check less numbers.

Output

Without Sieve
0:00:00.008019
With Sieve
0:00:00.075880

prime.py Used as a main class

def timeMethod(methodToTime, methodVar, methodVar2):
     #https://stackoverflow.com/questions/706721/how-do-i-pass-a-method-as-a-parameter-in-python
     start = datetime.now()
     if methodVar2 == None and methodVar == None:
          methodToTime()
     elif methodVar2 == None:
          methodToTime(methodVar)
     else:
          methodToTime(methodVar, methodVar2)

     end = datetime.now()
     time_elapsed = end - start
     return time_elapsed

if __name__ == "__main__": 
     import sys, SingleThreadPrimes
     print("Without Sieve")
     print(str(timeMethod(SingleThreadPrimes.getXPrimes, 1000, None)))
     print("With Sieve")
     print(str(timeMethod(SingleThreadPrimes.getXPrimesSieve, 1000, None)))
     #testSuite(SingleThreadPrimes.getXPrimesSieve, None, None)

SingleThreadedPrimes.py

import math

def getXPrimes(num):
     primeList = []
     primeList.append(2)
     candidate = 3
     while len(primeList) < num:
          isPrime = True
          for x in range(2, int(math.sqrt(candidate) + 1), 2):
               if candidate % x == 0:
                    isPrime = False
                    break
          if isPrime:
               primeList.append(candidate)
          candidate += 2
     return primeList


def getXPrimesSieve(num, primeList = None):
     if primeList == None:
          primeList = []
     if len(primeList) == 0:
          primeList.append(2)
          primeList.append(3)
     elif len(primeList) == 1:
          primeList.append(3)

     if num > len(primeList):
          candidate = int(primeList[len(primeList) - 1]) + 2
          while len(primeList) < num:
               isPrime = True
               for x in primeList:
                    x = int(x)
                    if candidate % x == 0:
                         isPrime = False
                         break
                    elif x > int(math.sqrt(candidate)):
                         break
               if isPrime:
                    primeList.append(candidate)
               candidate += 2
     return primeList

`Used as a main class`-?? I don't see any classes in that example.? — wwii, Dec 09 '19 at 23:35

ShadowRanger · Accepted Answer · 2019-12-09T23:28:55.790

Among other things, getXPrimes isn't actually finding primes (you only test divisibility by multiples of 2, which no odd number will ever fail), while getXPrimesSieve is, so you're comparing apples and oranges.

Beyond that getXPrimesSieve isn't doing much to improve performance, and is doing stuff that hurts it; it still has to perform many remaindering operations (a good sieve wouldn't); while it tries to avoid testing numbers above the square root of the number being tested, it does so by recomputing that square root for every prime to test, which is far more expensive than doing it once up front, as in getXPrimes.

Point is, you need to make your code both work and perform better than naive trial division. I suggest looking at useful sieving algorithms, e.g. for finding all primes up to a certain bound, the Sieve of Eratosthenes which amortizes the cost of "virtual" trial division without actually doing division or remaindering work at all, which would run considerably faster than either of your attempts.

Why this sieve method of finding primes is slower than a brute force

1 Answers1