我的问题直接来自CS圈子网站.这是对底部的最后一个问题这一页称为"引为起飞".基本纲要是他们想要一个1,000,001长度的列表,其中如果索引是素数,则每个项目的索引为True,而如果它不是素数,则每个项目的索引为False.
因此,例如,isPrime [13]是True.isPrime [14]是假的.
列表'isPrime'的第一点看起来像:
isPrime = [False, False, True, True, False, True, False, True, False, False, ...]
我的问题是他们有7秒的时间限制.我有一个下面的工作代码,数字较小,为101,用于调试目的.当我将它提升到所需的1,000,001列表长度时,它需要的时间太长,几分钟后我终于杀死了程序.这是我的工作(长度为101),代码非常慢:
n = 101
c = 2
isPrime = [False,False]
for i in range(2,n):
isPrime.append(i)
def ifInt(isPrime):
for item in isPrime:
if type(item) == int:
return item
for d in range(2,n):
if c != None:
for i in range(c,n,c):
isPrime[i] = False
isPrime[c] = True
c = ifInt(isPrime)
然后是我在这里找到的这个.它有一个更快的运行时间,但只输出一个素数列表,而不是一个n长度列表,list [n]返回True表示素数,否则返回false.
我不确定这个第二位代码是否真的能够在7秒内创建长度为1,000,001的素数列表,但这是我在研究中找到的最相关的东西.
def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes[i] = True
for i in primes:
factors = range(i,limitn, i)
for f in factors[1:]:
primes[f] = False
return [i for i in primes if primes[i]==True]
print primes_sieve1(101)
CS圈似乎很常用,但我无法为Python找到这个的工作版本.希望这对某人来说很容易解决.
这个问题不同于这一个,因为我不是想只有快速创建素数的列表,而是创建一个从0到n所有正整数由虚假的真实和非主要标记为总理的列表.
编辑:已经意识到在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
这是Sieve非常简单的实现.在继续之前,请确保您了解上面发生的事情.唯一需要注意的是你在i + i而不是i开始标记非素数,但这是显而易见的.(因为你认为我本身就是一个素数).为了公平地进行测试,所有数字都将高达2500万.
real 0m7.663s user 0m7.624s sys 0m0.036s
次要改进1(平方根):
我将尝试根据直接向不那么直接的变化对它们进行排序.注意我们不需要迭代到n,而只需要上升到n的平方根.原因是n下的任何复合数必须具有低于或等于n的平方根的素因子.当你手工筛选时,你会注意到n的平方根上的所有"未被发现"的数字都是默认的素数.
另一个注意事项是,当平方根变成一个整数时,你必须要小心一点,所以你应该在这种情况下添加一个,以便它覆盖它.IE,在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)等)
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
酷改进4(wim的想法):
此解决方案是一个相当高级的技巧.切片分配比循环更快,因此使用python的切片表示法.[R [开始:结束:跳过]
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分配一个数组,然后将half(均匀)设置为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整除与-1 mod 6一致.这表明我们每次可以跳过6并检查双方.无论是从我身边的糟糕实施,还是python内部,我都无法找到任何有意义的速度提升.:(
京公网安备 11010802040832号 | 京ICP备19059560号-6 