python - 这是最优素数生成器吗？

Question

这在任何方面都是寻找素数的最佳解决方案吗？我并不想在阳光下添加所有优化，但主要是好的吗？

def primesUpto(self, x):
    primes = [2]
    sieve = [2]
    i = 3
    while i <= x:
        composite = False
        j = 0
        while j < len(sieve):
            sieve[j] = sieve[j] - 1
            if sieve[j] == 0:
                composite = True
                sieve[j] = primes[j]
            j += 1
        if not composite:
            primes.append(i)
            sieve.append(i*i-i)
        i += 1
    return primes

Answer 1

嗯，很有趣。您的代码是真正诚实的真正的埃拉托色尼筛法 恕我直言，通过将它为遇到的每个质数设置的每个计数器递减 1，沿着递增的自然数计算它的方式在每一步。

而且效率很低。 Tested on Ideone它同时运行 empirical order of growth ~ n^2.2(在生成的几千个素数的测试范围内)作为著名的低效 Turner's trial division sieve (在 Haskell 中)。

为什么？几个原因。 首先，在你的测试中没有early bailout:当你检测到它是一个组合时，你继续处理计数器数组，sieve。由于第二个原因，您必须计算差异通过递减每个计数器在每个计数器上减 1步骤，其中 0 代表您当前的位置。这是原始筛恕我直言最忠实的表达，而且效率很低:今天我们的 CPU 知道如何在 O(1) 时间内添加数字(如果这些数字属于某个范围，0 .. 2^32，或者0 .. 2^64，当然)。

此外，我们的计算机现在也有直接存取存储器，计算出遥远的数字后，我们可以将其标记在随机存取数组中。这是埃拉托色尼筛法在现代计算机上效率的基础——直接计算和直接标记倍数。

第三个​​，也许是效率低下的最直接原因，是对倍数的过早处理:当你遇到 5 作为素数时，你将它的第一个倍数(尚未遇到)即 25 添加到计数器数组 sieve 中，马上(即当前点和倍数，i*i-i)。那太早了。 25 的加法必须推迟 直到……好吧，直到我们在递增的自然数中遇到 25。过早地开始处理每个素数的倍数(在 p 而不是 p*p)导致有太多的计数器需要维护 - O(n) 个(其中 n 是产生的素数的数量)，而不仅仅是 O(π(sqrt(n log n))) = O(sqrt(n/log n ))。

推迟优化when applied on a similar "counting" sieve in Haskell将 ~ n^2.3 .. 2.6 for n = 1000 .. 6000 primes 的经验增长顺序降低到 ~ n^1.5(速度明显提高)。当计数进一步被直接加法取代时，得到的测量经验增长阶数为 ~ n^1.2 .. 1.3 产生多达 hlaf 一百万个素数(尽管它很可能会在 ~ n^1.5 对于更大的范围)。