为什么这种寻找素数的筛选方法比bru慢

Question

python新手尝试在这里学习Prime查找程序

我知道这是一个常见的问题，从我的研究中我知道我可以做一些优化： 1） 预先分配一个固定的布尔数组，这样就不需要调整大小 2） 使用基本体而不是对象

然而，我仍然不明白为什么这个筛子慢得多，有什么想法吗？两者都使用附加到列表并对其进行迭代。我的直觉是筛子只需检查更少的数字

输出

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

prime.py用作主类

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

Answer 1

除此之外，getXPrimes实际上并没有找到素数（你只测试2的倍数的可除性，这是奇数不会失败的），而getXPrimesSieve是，所以你在比较苹果和橙子

除此之外getXPrimesSieve对提高性能没有多大作用，而且做了一些伤害性能的事情；它仍然需要执行许多剩余操作（一个好的筛子不会）；虽然它试图避免测试高于被测试数字平方根的数字，但它通过为每个要测试的素数重新计算该平方根来做到这一点，这比预先做一次要昂贵得多，如getXPrimes

关键是，您需要使您的代码既能工作又能比单纯的试用版更好地执行。我建议研究有用的筛选算法，例如，寻找所有达到某个界限的素数，the Sieve of Eratosthenes，它摊销“虚拟”试除法的成本，而不实际进行除法或剩余工作，这将比您的任何一次尝试都要快得多