擅长:python、mysql、java
<p>你的算法不是埃拉托斯提尼的筛子。您可以执行试除法(模运算符),而不是像两千多年前埃拉托什涅斯(Eratosthenes)那样去掉倍数。<a href="http://programmingpraxis.com/2009/02/19/sieve-of-eratosthenes/" rel="nofollow">Here</a>是对真筛选算法的一种解释,下面是我的简单、直接的实现,它返回一个不超过<em>n</em>的素数列表:</p>
<pre><code>def sieve(n):
m = (n-1) // 2
b = [True]*m
i,p,ps = 0,3,[2]
while p*p < n:
if b[i]:
ps.append(p)
j = 2*i*i + 6*i + 3
while j < m:
b[j] = False
j = j + 2*i + 3
i+=1; p+=2
while i < m:
if b[i]:
ps.append(p)
i+=1; p+=2
return ps
</code></pre>
<p>我们只筛选奇数,停在<em>n</em>的平方根。对3、5、7、9等整数之间的<em>j</em>映射的奇数计算。。。索引0,1,2,3。。。在<em>b</em>位数组中。在</p>
<p>您可以在<a href="http://ideone.com/YTaMB" rel="nofollow">http://ideone.com/YTaMB</a>处看到这个函数的作用,它在不到一秒钟的时间内将素数计算到一百万。在</p>