Eratosthenes的筛子-寻找素数Python
只是为了澄清，这不是一个家庭作业问题:)
我想为我正在构建的一个数学应用程序找到素数，却遇到了方法。
我已经用Python编写了它的实现。但它的速度非常慢。比方说，如果我想找到所有小于2百万的素数。它需要> 20分钟。(我在这里停止了它)。我怎么才能加快速度呢？
def primes_sieve(limit):
limitn = limit+1
primes = range(2, limitn)
for i in primes:
factors = range(i, limitn, i)
for f in factors[1:]:
if f in primes:
primes.remove(f)
return primes
print primes_sieve(2000)更新：，我最终对这段代码进行了分析，发现从列表中删除一个元素花费了相当多的时间。考虑到它必须遍历整个列表(最坏的情况)来找到元素&然后删除它，然后重新调整列表(可能会继续一些复制？)，这是可以理解的。不管怎么说，我扔掉了字典的清单。我的新实现-
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(2000000)回答 21
Stack Overflow用户
发布于 2010-10-15 19:54:15
您没有完全实现正确的算法：
在您的第一个示例中，primes_sieve不维护要删除/取消设置的素数标志列表(就像在算法中一样)，而是连续地调整整数列表的大小，这是非常昂贵的:从列表中删除一项需要将所有后续项向下移动一位。
在第二个示例中，primes_sieve1维护了一个素数标志字典，这是朝着正确方向迈出的一步，但它以未定义的顺序迭代字典，并冗余地删除因子的因子(而不是像算法中那样只删除素数的因子)。您可以通过对键进行排序来解决这个问题，并跳过非素数(这已经使它快了一个数量级)，但直接使用列表仍然要高效得多。
正确的算法(使用列表而不是字典)如下所示：
def primes_sieve2(limit):
a = [True] * limit # Initialize the primality list
a[0] = a[1] = False
for (i, isprime) in enumerate(a):
if isprime:
yield i
for n in range(i*i, limit, i): # Mark factors non-prime
a[n] = False(请注意，这还包括从素数的平方(i*i)而不是双精度开始非素数标记的算法优化。)
Stack Overflow用户
发布于 2014-01-05 02:01:55
def eratosthenes(n):
multiples = []
for i in range(2, n+1):
if i not in multiples:
print (i)
for j in range(i*i, n+1, i):
multiples.append(j)
eratosthenes(100)Stack Overflow用户
发布于 2010-10-15 13:27:02
从数组(列表)的开头删除需要向下移动它后面的所有项。这意味着以这种方式从前面开始删除列表中的每个元素是一个O(n^2)操作。
使用set可以更有效地完成此操作：
def primes_sieve(limit):
limitn = limit+1
not_prime = set()
primes = []
for i in range(2, limitn):
if i in not_prime:
continue
for f in range(i*2, limitn, i):
not_prime.add(f)
primes.append(i)
return primes
print primes_sieve(1000000)..。或者，避免重新排列列表：
def primes_sieve(limit):
limitn = limit+1
not_prime = [False] * limitn
primes = []
for i in range(2, limitn):
if not_prime[i]:
continue
for f in xrange(i*2, limitn, i):
not_prime[f] = True
primes.append(i)
return primeshttps://stackoverflow.com/questions/3939660
复制相似问题