为什么这种查找素数的筛子方法比蛮力慢

Question

Python的新手尝试在此处使用Prime Finding程序学习！

我知道这是一个普遍的问题，根据我的研究，我知道可以做一些优化：1）预分配固定的布尔数组，因此无需调整大小2）使用基本体而不是对象

但是，我仍然不明白为什么这个筛子要慢得多，有什么想法吗？两者都使用追加到列表并遍历它们。我的直觉是筛子只需要检查less个数字。

输出

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可以执行除以[[no]]或进行余数运算，并且比任何一次尝试都快得多。