帮助将 CF 高斯的素数假设添加到我的埃拉托色尼筛中

Question

嘿大家！ 所以我几乎已经完成了我开始为学校解决的一个涉及埃拉托色尼筛的问题。我设法让程序打印出从 2 到 1000 的平方根的所有素数。但是，我的老师要求我使用 CF 高斯的素数假设（？）。他是这么说的： CF高斯假设定义(N)小于或等于N的素数个数 当 N 接近无穷大时，(N) = N/loge(N)。这被称为素数 假设。在 for 循环中打印素数，一个指示其序数的计数器 数字（1、2、3 等）和 (N) 的值。

我尝试制作另一个 for 循环，并打印素数，但它对我不起作用！ :( 呃。 任何帮助将不胜感激！ :)

import math
def sieves(N): 
    x = 1000*[0]        
      prime = 2
      print('2')
      i = 3
      while (i <= N):
         if i not in x:
            print(i)
            prime += 1
            j = i
            while (j <= (N / i)):
               x.append(i * j)
               j += 1
         i += 2
      print("\n")
def main():
    count = 0
    for i in range (1000):
       count = count + 1
    print(sieves(math.sqrt(1000)))

main()

Answer 1

问题似乎出在 j=i 行。您希望开始 j = 1，以便捕获 i 的所有倍数并将它们添加到非素数元素的“x”列表中。如果你开始 j = i 你会错过一些。当您测试“i not in x”时，对于某些非素数，它将评估为 true。

另外，您可能指的是 x[i*j] = 1 （即设置为 1 意味着 i*j == 非素数），而不是 x.append(i*j)
通过该修改，“i not in x”可以优化为“x[i] == 0”，无需搜索整个数组。这比保留稀疏数组“x”并且必须在循环中的每一步搜索它的元素要有效得多。