0

大家好！所以我几乎完成了一个我开始为学校处理的涉及埃拉托色尼筛的问题。我设法让程序打印出从 2 到 1000 的平方根的所有素数。但是，我的老师要求我使用 CF Gauss 的素数假设（？）。这就是他所说的：CF Gauss 假设 (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()
4

1 回答 1

0

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

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

于 2011-05-01T21:42:50.790 回答