我意识到在SO上有很多针对素数筛法的优化,但其他人很少解释它们,因此对初学者或第一次创建该算法的人来说,这些优化很难接近。这里所有的解决方案都是用Python编写的,以达到相同的速度和最优化。这些解决方案将逐渐变得更快,更复杂。 :)
基本解决方案
def primesVanilla(n):
r = [True] * n
r[0] = r[1] = False
for i in xrange(n):
if r[i]:
for j in xrange(i+i, n, i):
r[j] = False
return r
这是一个非常直观的筛法实现。在继续之前,请确保您理解上面发生的事情。唯一需要注意的是,您从i+i(而不是从i)开始标记非质数,但这是相当明显的。(因为您假设i本身是一个质数)。为了使测试公平,所有数字将针对列表最多2500万个进行。
real 0m7.663s
user 0m7.624s
sys 0m0.036s
小改进1(平方根):
我会尝试按照直截了当到不那么直截了当的顺序进行排序。请注意,我们不需要迭代到n,而是只需要到n的平方根。原因是在n以下的任何合数,必须具有小于或等于n的平方根的质因子。当您手动筛选时,您会注意到所有“未筛选”的大于n的平方根的数字默认为质数。
另一个要注意的是,当平方根是整数时,必须要小心一点,所以在这种情况下应该加上一,以覆盖它。例如,在n = 49时,您希望循环到7(包括7),否则您可能会得出49是质数的结论。
def primes1(n):
r = [True] * n
r[0] = r[1] = False
for i in xrange(int(n**0.5+1)):
if r[i]:
for j in xrange(i+i, n, i):
r[j] = False
return r
real 0m4.615s
user 0m4.572s
sys 0m0.040s
请注意,这样做要快得多。当您考虑到它时,您只需要循环到平方根,所以现在需要2500万个顶级迭代的东西现在只需要5000个顶级迭代。
小改进2(在内部循环中跳过):
观察一下,在内部循环中,我们可以从i * i开始而不是从i + i开始。这与平方根的情况非常相似,但大的想法是i和i * i之间的任何复合数已经被较小的质数标记过了。
def primes2(n):
r = [True] * n
r[0] = r[1] = False
for i in xrange(int(n**0.5+1)):
if r[i]:
for j in xrange(i*i, n, i):
r[j]=False
return r
real 0m4.559s
user 0m4.500s
sys 0m0.056s
嗯,有点令人失望。但是,嘿,它仍然更快了。
较大的改进3(甚至跳过):
这里的想法是我们可以预先标记所有偶数索引,然后在主循环中每2次迭代跳过一次。之后,我们可以从3开始外部循环,内部循环可以跳过2 * i。 (因为按i进行循环意味着它将是偶数,(i+i) (i+i+i+i)等等)
def primes3(n):
r = [True] * n
r[0] = r[1] = False
for i in xrange(4,n,2):
r[i] = False
for i in xrange(3, int(n**0.5+1), 2):
if r[i]:
for j in xrange(i*i, n, 2*i):
r[j] = False
return r
real 0m2.916s
user 0m2.872s
sys 0m0.040s
Cool Improvements 4(wim的想法):
这个解决方案是一个相当高级的技巧。切片赋值比循环更快,因此它使用Python的切片符号:r[begin:end:skip]
def primes4(n):
r = [True] * n
r[0] = r[1] = False
r[4::2] = [False] * len(r[4::2])
for i in xrange(3, int(1 + n**0.5), 2):
if r[i]:
r[i*i::2*i] = [False] * len(r[i*i::2*i])
return r
10 loops, best of 3: 1.1 sec per loop
轻微改进 5
请注意,Python在计算长度时会重新切片r[4::2]
,因此这会花费相当多的额外时间,因为我们所需的只是计算长度。不过,我们确实使用了一些不好的数学方法来实现这一点。
def primes5(n):
r = [True] * n
r[0] = r[1] = False
r[4::2] = [False] * ((n+1)/2-2)
for i in xrange(3, int(1 + n**0.5), 2):
if r[i]:
r[i*i::2*i] = [False] * ((n+2*i-1-i*i)/(2*i))
return r
10 loops, best of 3: 767 msec per loop
作业加速(Padraic Cunningham):
注意,我们分配一个包含全部 True 值的数组,然后将一半(偶数位)设置为 False。实际上,我们可以直接使用交替的布尔数组。
def primes6(n):
r = [False, True] * (n//2) + [True]
r[1], r[2] = False, True
for i in xrange(3, int(1 + n**0.5), 2):
if r[i]:
r[i*i::2*i] = [False] * ((n+2*i-1-i*i)/(2*i))
return r
10 loops, best of 3: 717 msec per loop
不要引用我的话,但我认为在没有一些复杂的数学方法的情况下,对于这个最新版本没有明显的改进。我尝试过一个聪明的方法,但并没有变得更快,即注意到除了2和3之外的素数必须是6k + 1或6k-1的形式。(请注意,如果它是6k,则可被6整除,6k + 2 | 2,6k + 3 | 3,6k + 4 | 2,6k + 5与模6同余于-1。这表明我们可以每次跳过6并检查两侧。但无论是因为我实现得不好还是Python内部的原因,我都无法找到任何有意义的速度提升。 :(
print list(sieve.primes_sieve2(10000000))
在不到7秒的时间内运行。它比你的问题大10倍,并在内部生成了问题中所需的列表。你所要做的就是将其取出即可。 - pvg