Python 中的埃拉托斯特尼筛法

我正在尝试编写一个python函数来返回小于给定值的素数个数以及所有素数的值。我需要使用埃拉托斯特尼筛法算法。我相信我在函数中遗漏了一些东西 - 例如，当我想找到 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

“我被告知我需要使用平方根”。你认为这是为什么？通常，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.