Решето Эратосфена, оставляющее некоторые составные части

Я попытался возиться с цифрой 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)]

Более длинный ответ/как я туда попал: Ваше первое range(1000) равно 0, 1000. Ваше второе range(floor(1000/index))т.е. 0, 1 Я считаю, что это должно быть так, потому что, насколько я понимаю, floor() даст вам наибольшее целочисленное значение, меньшее или равное x. Для range(floor(1000/index)) диапазон никогда не будет больше единицы, потому что он переходит в число с плавающей запятой (1000/999), что дает диапазон 0, 1. Теперь, если вы используете `range (этаж((999/индекс)+1) вы заканчиваетесь диапазоном 0, 2.

Сейчас экспериментирую, вроде если делать range(n), range(floor((n-1/index)+1) работает.

Я распечатал диапазон x, index, product x*index для каждой итерации: для первого набора параметров, который вы использовали, он только циклически переходил к 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)

Далее: я думаю, вы, возможно, неправильно понимаете, как должно работать сито или как на самом деле работает диапазон. С решетом вы будете перебирать числа гораздо меньше раз, особенно когда вы идете вверх, в этом часть его полезности: вы отмечаете кратные каждому простому восходящему числу, поэтому вам не нужно ни выполнять исчерпывающие тесты для каждого числа, чтобы найти его составность или первичность. вы просто исключаете числа, кратные каждому последующему простому числу 2*(1...n), 3*(1...n), [4 уже исключено], 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)

Подумайте о том, когда 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.