Eratosthenes筛留出一些复合材料

Question

编辑：好的，所以代码现在工作...任何人都可以解释为什么改变Floor(1000/index)到floor(999/index) + 1帮助？

我的Eratosthenes Sieve的实现将列表中的一些复合材料列为素数。也就是说，如果我发现的素数，直到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

Answer 1

我试图与1000图搞乱列出的999是3和37 prime_list

素因数列出，看它是否会显示出同样的行为，因为你只能看到错误的输出接近极限，并且看起来错误的非质数保存在接近极限的列表中（无论你设置它，我尝试了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)]

更长的答案/我如何到达那里： 你的第一个range(1000)为0，1000 你的第二个是range(floor(1000/index))即0,1 我相信它必须是因为，据我所知，floor()会给你最大的整数值小于或等于x。对于range(floor(1000/index))，范围将永远不会大于1，因为它会浮动（1000/999），给出范围0,1。 现在，如果您使用范围（floor（（999/index）+1），则以范围0，2

现在尝试，看来如果你range(n)，range(floor((n-1/index)+1)它的工作原理

我打印出来的X，指数，商品X *指数范围为每次迭代：对于第一套你只能使用参数循环到x = 23，index = 42，所以它永远不会返回989，与999相同，它永远不会循环通过索引和x的任何组合，等于999.当通过增加范围一，它达到了所有这些迭代，你必须减少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，所以它更清晰。只有倍数“迭代”

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之间的值。