python - 埃拉托斯特尼筛法遗漏了一些复合 Material

Question

编辑:好的，代码现在可以运行了...任何人都可以解释为什么将 Floor(1000/index) 更改为 floor(999/index) + 1有帮助吗？

我对埃拉托斯特尼筛法的实现是在列表末尾列出一些复合 Material 作为素数。也就是说，如果我找到 1000 之前的素数，则还包括 980 到 1000 之间的一些非素数

from math import floor

prime_list = []
list_primes2 = [True for x in range(1000)]
list_primes2[0], list_primes2[1] = False, False

for index, value in enumerate(list_primes2):
    if value:
        for x in range(floor(999/index)+1):
            list_primes2[index*x] = False

        prime_list.append(index)

print(prime_list)

以上代码得出 1000 以内的所有素数加上 989 和 999

989的质因数是23和43，两者都列在prime_list

999的质因数是3和37，两者都列在prime_list

Answer 1

考虑一下当index = 3时。此处，floor(1000/index) = 333 和 range(333) 生成 0 到 332 之间的值。因此，list_primes2[999]未设置为False。

另一方面，floor(999/index) + 1 = 334 和 range(334) 生成 0 到 333 之间的值。

一般来说，该语句的结构应该是floor(max/index) + 1。请注意，语句 ceil(max/index) 并不等效。从上面的示例中可以很容易地看出这一点，其中 ceil(max/index) 只会再次生成 0 到 332 之间的值。