这比厄拉多塞的筛子更有效吗？

Question

我用Python2.7编写了一段代码，用于创建质数列表。代码是

def primes_list(num):
    ans = [2]
    for i in range(3, num, 2):
        for j in ans:
            if i % j == 0:
                break
        else:
            ans.append(i)
    else:
        return ans

这是否比埃拉托斯特尼筛更有效？我认为记忆效率应该更好，但我怀疑时间效率。如何计算时间和内存效率，以及如何对效率进行基准测试？

Answer 1

测量增长的经验顺序，就是这样！:)

例如，对于来自已接受答案的数据，log_10（50.41/0.9） = 1.75，log_10（2.31/0.21） = 1.04，因此您的TD（试验除法）代码（在1，000范围内）的生长顺序约为n^1.75经验增长顺序。10，000） vs. ~ n^1.04 埃拉托斯特尼筛子。

后者符合< code>n log log n，而前者符合n^2 / log(n)^2，这是理所应当的。

用< code>g(n) = n^2 / log(n)^2，我们得到< code > g(10000)/g(1000)= 56.25 ，这与经验值< code>50.41/0.9 = 56.01仅相差0.4%。但是对于< code>g2(n) = n^2 / log(n)，我们得到< code > G2(10000)/G2(1000)= 75 ，这与证据相差甚远。

关于时间复杂性：事实上，大多数复合材料都很早就失效了（是小素数的倍数）。要生成k=n/log（n）素数，这里需要O（k^2）时间，通过所有前面的素数测试每个素数，仅测试那些不超过其平方根的素数。

复合物不会增加复杂性（M. ONeill的JFP文章（第4页）中的精确分析给出了与测试sqrt时素数相同的复合物复杂性 - 每个复合材料的素因数保证不大于其sqrt - 因此复合材料的复杂性甚至低于此处素数的复杂性）。

所以总的来说，它是O（k^2），也就是说，O（n^2/对数（n）^2）。

只需添加两行代码，就可以大大提高代码的速度，从O（n^2/log（n）^2）到O（n*1.5/log（n

    for j in ans: 
        if j*j > i: 
            ans.append(i); break; 
        if i % j == 0:
            break
    # else:
    #     ans.append(i)

时间复杂性的提高意味着10000与1000的运行时间比17.8x，而不是像以前那样56.25x。这意味着在此范围内的经验增长顺序为~n^1.25（而不是~n^1.75）。10000次调用的绝对运行时间将比原来的50.41秒更接近2.31秒。

顺便说一句，你的原始代码相当于大卫特纳的著名代码，

primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, rem y x /= 0]

和改进的代码，如下所示：

primes = 2 : sieve [3..] primes 
sieve xs (p:ps) | (h,t) <- span (< p*p) xs =
              h ++ sieve [y | y <- t, rem y p /= 0] ps 

（代码在哈斯克尔，我认为它具有足够的可读性。x：xs 代表一个列表，其中 x 是 head 元素，x 是列表的其余部分）。

Answer 2

不，这是试验除法，在时间复杂度上比eratosthenes的筛子差得多。它的空间复杂度稍微好一点，但是，由于素数大约是n/log（n），所以你没有节省大量的内存。此外，筛子可以使用位向量来完成，它可以将常数减少32/64倍（因此出于实际目的，它可能会更好）。

显示计时差异的小型基准测试:

>>> timeit.timeit('primes_list(1000)', 'from __main__ import primes_list', number=1000)
0.901777982711792
>>> timeit.timeit('erat(1000)', 'from __main__ import erat', number=1000)
0.2097640037536621

如您所见，即使使用n=1000eratothenes，其速度也要快4倍以上。如果我们将搜索增加到10000：

>>> timeit.timeit('primes_list(10000)', 'from __main__ import primes_list', number=1000)
50.41101098060608
>>> timeit.timeit('erat(10000)', 'from __main__ import erat', number=1000)
2.3083159923553467

现在eratosthenes要快21倍。正如你所看到的，很明显eratosthenes要快得多。

使用numpy数组可以很容易地将内存减少32或64（取决于您的机器架构），并获得更快的结果：

>>> import numpy as np
>>> def erat2(n):
...     ar = np.ones(n, dtype=bool)
...     ar[0] = ar[1] = False
...     ar[4::2] = False
...     for j in xrange(3, n, 2):
...             if ar[j]:
...                     ar[j**2::2*j] = False
...     return ar.nonzero()[0]
... 
>>> timeit.timeit('erat2(10000)', 'from __main__ import erat2', number=1000)
0.5136890411376953

另一个比另一个筛子快4倍。

Answer 3

你正在做的是试验除法 - 测试每个候选素数与它下面的每个已知素数。在调用范围中跳过奇数将为您节省一些除法，但这正是筛分所基于的技术：您知道每秒的数字都可以被2整除，因此是复合的。筛子只是将其扩展到：

• 每三个数可以除以三，因此是复合数
• 每五乘五，因此合成

诸如此类。由于Sieve被认为是最省时的算法之一，而trial division被认为是最省时的算法之一(维基百科将Sieve描述为< code>O(n log log n)，根据下面的评论，您的算法可能是O(n^2 / log n))，因此有理由假设带有一些类似sieve的优化的trial division达不到筛分的要求。