Python中的Eratosthenes的筛选器

我正在尝试编写一个python函数来返回小于给定值和所有素数值的素数数目。我需要使用Eratosthenes的Sieve算法。我相信我在函数中缺少了一些东西 - 例如，当我想找到100以下的素数时。我得到的全部是2,3,5,7。我意识到如果我不使用“平方根” ，我可以得到所有我需要的素数;但我被告知我需要在那里包含平方根。有人可以看看我的代码，让我知道我错过了什么吗？谢谢你的时间。Python中的Eratosthenes的筛选器

def p(n): 
is_p=[False]*2 + [True]*(n-1) 
for i in range(2, int(n**0.5)): 
    if is_p[i]: 
     yield i 
     for j in range(i*i, n, i): 
      is_p[j] = False

来源

2013-06-27 user2203774

“我被告知需要使用平方根”。你为什么这么认为？通常E的筛选用于从列表中移除所有“非首要”数字;你可以通过找到一个素数来做到这一点，然后检查列表中所有素数的倍数。下一个数字“未检查”是您的下一个素数 - 您报告它（使用yield），然后再次检查。您只需检查小于平方根的因数 - 大于平方根的因子具有小于平方根的相应因子，因此它们已被发现。

不幸的是，当打印出素数时，你不能“停在中间”。例如，101是主要的;但如果你只循环到11，你将永远不会发现它在那里。所以，我们需要有两个步骤：

1）遍历所有“可能的倍数” - 在这里，你可以去“只到平方根”

2）检查列表对于尚未所有数字被检查过 - 在这里你必须“走一路”

这使得下面的代码：

def p(n): 
    is_p=[False]*2 + [True]*(n-1) 
    for i in range(2, int(n**0.5)): 
    if is_p[i]: 
     for j in range(i*i, n, i): 
      is_p[j] = False 
    for i in range(2, n): 
    if is_p[i]: 
     yield i 

print list(p(102))

结果是素数的直至并包括101列表。

来源

2013-06-27 22:16:18 Floris

您的逻辑是正确的，除了for循环。它在达到sqrt(n)-1后终止。对于p(100)，它将只运行从2到9.因此，您只能得到素数数字直到9.

来源

2013-06-27 22:09:17 Nik

我在这里应该提到，你的逻辑确实找到了直到n的所有素数，即'is_p'只有for循环结束时的素数索引具有'True'。唯一的问题是'产量'没有足够的次数。 – Nik

感谢您的提示！真的很感激它！ – user2203774

您对平方根的使用会提前终止您的结果。如果你想yield所有的素数多达100个，你的循环已经去到100

平方根，因为它是在你的第二个for循环暗示没有必要在你的代码。如果i*i < n则i < sqrt(n)。

来源

2013-06-27 22:21:27

感谢您的提示！真的很感激它！ – user2203774

Python中的Eratosthenes的筛选器

回答

相关问题