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

Question

新手 python 尝试在这里使用 Prime Finding 程序学习！

我知道这是一个常见问题，根据我的研究，我知道我可以进行一些优化： 1) 预先分配一个固定的布尔值数组，因此不需要调整大小 2) 使用原语而不是对象

然而，我还是不明白为什么这个筛子这么慢，有什么想法吗？两者都使用附加到列表并迭代它们。我的直觉是筛子只需要检查 less 个数字。

输出

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

prime.py用作主class

def timeMethod(methodToTime, methodVar, methodVar2):
     #
     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 分摊了 "virtual" 试验除法的成本，而根本没有实际进行除法或余数工作，这运行比你的任何一个都快得多尝试。

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

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

python

primes