这是一个最优的素数发生器吗？

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

嗯，很有趣。你的代码实际上是诚实对善的真正的EratosthenesIMHO，它沿着递增的自然数计数，每一步减少它为每个质数设置的每个计数器1。在

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

为什么？几个原因。首先，不早期救助在您的测试中：当您检测到它是一个组合时，您继续处理计数器数组，sieve。你必须，因为第二个原因：你在每一步的每一个计数器递减1，0代表你的当前位置。这是原始筛子IMHO最忠实的表达方式，而且效率很低：今天我们的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))。在

对于n = 1000 .. 6000素数，延迟优化when applied on a similar "counting" sieve in Haskell将其经验增长顺序从~ n^2.3 .. 2.6降低到刚好高于{}（速度明显有巨大的提高）。当计数被直接加法进一步取代时，所测得的经验增长阶数是~ n^1.2 .. 1.3，产生高达100万个素数（尽管在更大的范围内，它很可能在~ n^1.5上获得）。在