0

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

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
4

3 回答 3

4

“我被告知我需要使用平方根”。你认为这是为什么？通常 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-27T22:16:18.643 回答
2

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

于 2013-06-27T22:09:17.083 回答
1

您对平方根的使用会提前终止您的结果。如果你想让yield所有素数都达到 100，那么你的循环必须达到 100。

平方根在您的代码中不是必需的，因为它隐含在您的第二个for循环中。如果i*i < n那么i < sqrt(n).

于 2013-06-27T22:21:27.070 回答