埃拉托色尼筛法遗漏了一些复合材料

Question

编辑：好的，所以代码现在可以工作了...谁能解释为什么将 Floor(1000/index) 更改为 floor(999/index) + 1 有帮助？

我的埃拉托色尼筛法的实现是在列表的末尾列出一些复合材料作为素数。也就是说，如果我要找到直到 1000 的素数，一些 none 介于 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

我试着弄乱 1000 图看它是否会表现出相同的行为，因为你只看到接近极限的错误输出，而且错误的非素数似乎保留在列表接近极限（随便你设置，我试了2000）。

简短回答：问题似乎是，由于您的 range(float(1000/index)) 元素的运作方式，您正在削减一些接近上限的值。它不会遍历它们，也不会从您的素数列表中取出它们。

如果您在该范围内加 1 它会起作用，也就是说，它会遍历它需要的所有数字，但是您必须将 1000 减少到 999 以防止乘积上升到 1000 以上（即 x in range(floor(1000/index)+1)).否则该产品 >999 并引用超出您设置的原始范围的列表索引：list_primes2 = [True for x in range(1000)]

更长answer/how我到达那里： 你的第一个 range(1000) 是 0, 1000。你的第二个是 range(floor(1000/index))ie 0, 1 我认为必须如此，因为据我了解，floor() 会给你 小于或等于 x 的最大整数值。 对于 range(floor(1000/index))，范围永远不会大于一，因为它转到 float(1000/999) 给出范围 0、1。现在，如果您使用 `range(floor((999/index)+1) ，您将以范围 0、2.

结束

现在正在试验，似乎如果你这样做 range(n)，range(floor((n-1/index)+1) 就可以了。

我打印出每次迭代的 x, index, product x*index 范围：对于你使用的第一组参数，它只是循环到 x=23，index=42，所以它永远不会返回989，与 999 相同，它从未循环遍历等于 999 的索引和 x 的任何组合。当您将范围增加一个时，它会达到所有这些迭代。您必须将 1000 减少到 999 以防止产品上升到 1000 以上（即 x in range(floor(1000/index)+1)）并引用超出您设置的原始范围的列表索引：list_primes2 = [True for x in range(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(1000/index)):
            print (x)
            print (index)
            print (x*index)
            print (range(floor(1000/index)))
for index, value in enumerate(list_primes2):
    if value:
        for x in range(floor(1000/index)):
            list_primes2[index*x] = False
        prime_list.append(index)
print(prime_list)


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):
            print (x)
            print (index)
            print (x*index)
            print(range(floor(999/index)+1))

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)

进一步：我认为您可能误解了 Sieve 的工作原理，或者范围的实际工作原理。使用筛子，您迭代的次数会少得多，尤其是当您向上移动时，这是有用的一部分：您标记每个上升的素数的倍数，因此您无需对每个数字执行详尽的测试以找到它的复合性或素数。你只需消除每个连续素数的倍数 2*(1...n), 3*(1...n), [4 已经是 elim], 5*(1...n) 直到你得到 n .

我们将转到 20，以便更清楚。只有倍数是"iterated over"

So  
x-[Eliminating]               [All Eliminated]                
2-[4,6,8,10,12,14,16,18,20]   [4,6,8,10,12,14,16,18,20]
3-[6,9,15]                    [4,6,8,9,10,12,14,15,16,18,20]
5-No more multiples <20       [4,5,6,8,9,10,12,14,15,16,18,20]          
7-No more multiples <20       [4,5,6,8,9,10,12,14,15,16,18,20]
11-No more multiples <20      [4,5,6,8,9,10,12,14,15,16,18,20]
13-No more multiples <20      [4,5,6,8,9,10,12,14,15,16,18,20]
17-No more multiples <20      [4,5,6,8,9,10,12,14,15,16,18,20]
19-No more multiples <20      [4,5,6,8,9,10,12,14,15,16,18,20]

所以我们可以看到0-10是4步，远远少于你的函数运行。

我们可以像我之前的回答一样进行测试，它证明了这一点，即使我们将限制设置为低至 10，也有 13 次迭代 - 比数量多。

from math import floor
prime_list = []
iterations=0
list_primes2 = [True for x in range(10)]
list_primes2[0], list_primes2[1] = False, False
for index, value in enumerate(list_primes2):
    if value:
        for x in range(floor(9/index)+1):
            iterations+=1
            print ("Iterations:",iterations)
            list_primes2[index*x] = False
            print ("X:         ",x)
            print ("index:     ",index)
            print ("x*index:   ",x*index)
            print(range(floor(9/index)+1))
            print("Numbers now in list of primes: ",prime_list)
            print()
        prime_list.append(index)

print("List of primes: ",prime_list)

Answer 2

想想什么时候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 之间的值。

埃拉托色尼筛法遗漏了一些复合材料

Sieve of Eratosthenes leaving out some composites

python

sieve-of-eratosthenes

python-3.x