1

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

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
4

1 回答 1

4

嗯，很有意思。您的代码实际上是诚实的 Eratosthenes恕我直言的真正筛子，通过将它为遇到的每个素数设置的每个计数器递减，每一步减 1，沿着递增的自然数计数。

而且效率非常低。在 Ideone 上进行测试，它以与著名的低效特纳试验除法筛（在 Haskell 中）相同的经验增长顺序 ~ n^2.2运行（在产生的几千个素数的测试范围内）。

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

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

第三，也许是效率低下最直接的原因，是对倍数的过早处理：当您遇到 5 作为素数时，您立即将其第一个倍数（尚未遇到）即 25 添加到计数器数组中，sieve（即当前点与倍数之间的距离，i*i-i)。这太快了。25 的加法必须推迟到……好吧，直到我们在升序自然数中遇到 25。开始过早地处理每个素数的倍数（在p而不是p*p）导致有太多的计数器需要维护 -O(n)其中（n产生的素数的数量在哪里），而不是仅仅O(π(sqrt(n log n))) = O(sqrt(n / log n)).

当在 Haskell 中应用于类似的“计数”筛子时，延迟优化将其经验增长顺序从素数降到略高于（显然速度上的巨大提升）。当计数被直接加法进一步取代时，由此产生的测量经验增长顺序是产生多达一百万个素数（尽管它很可能会在更大的范围内获得收益）。~ n^2.3 .. 2.6n = 1000 .. 6000~ n^1.5~ n^1.2 .. 1.3~ n^1.5

于 2013-05-31T23:35:48.623 回答