Решето Эратосфена – алгоритм определения простых чисел. Решение задачи на Python

Решето Эратосфена – это алгоритм, оставляющий в ряду натуральных чисел только простые числа.
Первым простым числом считается двойка.
Здесь зачеркнуты составные числа. А 2, 3, 5, 7, 11, 13, 17 являются простыми, их нельзя разделить ни на какое предшествующее им другое простое число. Если же число составное, то оно раскладывается на простые множители, то есть должно делиться на что-то впереди стоящее.

Алгоритм решета Эратосфена заключается в том, что сначала ряд натуральных чисел просматривается на наличие в нем всех чисел, кратных двум. Потому что если число больше двух и делится на 2, значит оно составное. Все четные, кроме двойки, вычеркиваются из ряда.
Следующее число – это 3. Оно априори простое, потому что иначе делилось бы на какое-нибудь число, стоящее до него, и было бы уже вычеркнуто.
Теперь из ряда удаляются все числа, кратные трем, то есть каждое третье, начиная с тройки. Понятно, что какие-то из чисел были удалены ранее, на этапе проверки кратности к двойке. Но это не страшно.
Следующее за тройкой натуральное число – это 4. Его уже нет, так как оно было кратно двойке. Это составное число.
Следующее число – пятерка. Она не затерта, следовательно это простое число.
Вычеркиваем из ряда все числа, кратные пятерке. И так далее.

Теперь напишем программу на Python.
В переменной n будет храниться последнее натуральное число ряда.
Создадим список целых чисел до n включительно. У нас индексы ячеек будут совпадать с их значениями. Например, в ячейке с индексом 2, находится число 2. Так алгоритм и программа будут проще.
Будем из ряда убирать все непростые числа, заменяя их нулями.
Число 1 нам не нужно, поэтому сразу записываем в ячейку 0.
Цикл начнется с двойки. Пока i меньше n. На самом деле здесь можно как минимум разделить на 2, потому что когда i равна половине ряда, то i + i будет равно последнему элементу ряда. То есть перебирать числа после прохождения половины смысла нет. А еще на самом деле тут можно извлечь корень из n.
Если текущая ячейка не забита нулем, значит мы встретили очередное простое число.
Будем вычеркивать кратные ему числа.
Первое кратное будет в 2 раза больше, чем i.
Поскольку надо будет добавлять i множество раз, понадобится цикл.
Пока j меньше или равно n, в ячейку j записываем 0. И увеличиваем j на величину i.
Не забываем в конце внешнего while перейти к следующему натуральному числу.

Посмотрим, что получилось.
Вместо составных чисел стоят нули. Чтобы избавиться от них, можем создать другой список.

Данный алгоритм можно улучшить. Есть определенные математические закономерности. И здесь можно не удваивать i, а сразу возводить в квадрат. Здесь, как уже было сказано, можно извлечь квадратный корень из n. Это то же самое, что возвести в степень 0.5. Все это уменьшит количество проходов по циклам.

Это прокомментированный пример без оптимизации алгоритма. Здесь список заполняется обычным способом, а не с помощью выражения-генератора списка.
От нулей избавляемся через превращение списка во множество. Во множестве как известно не бывает одинаковых значений. Остается один ноль, его удаляем. И превращаем множество обратно в список.

[Fravije]

Добрый день!
Спасибо за интересную задачу. Уже не первый раз нахожу ваш канал при поиске решений задач.

На одном ресурсе я нашел такое решение задачи (там демонстрировали пример с флагом):

num = int(input())
flag = True

for i in range(2, num):
if num % i == 0: # если исходное число делится на какое-либо отличное от 1 и самого себя
flag = False

if num == 1:
print('Это единица, она не простая и не составная')
elif flag == True:
print('Число простое')
else:
print('Число составное')

Я подумал - а что если перефразировать данную задачу.
Например, я не ввожу числа для проверки на простое / сложное, а проверка идет автоматически и непрерывно.
Если число сложное, то новый поиск, если простое - оно записывается в столбик. В итоге имеем растущий столбик:
2
3
5
7
11
и т.д.

Я начинал решать через

while True:

for i in range(2, num):

но как ни вертел, все выдавались ошибки. Возможно, я взялся за что-то слишком сложное для своего уровня...

У вас есть что-то подобное? Или может сняли бы ролик для такого решения?

[VitalayManin]

плохо работает. как найти делители. 2^1277-1 можно ли одновременно находить простые числа и числа с их делителями.

[abyssvoid]

При n=50, выдает числа до 31 включительно (последнее должно быть 47). Причем при n=100, работает корректно. Как так?

[АндрейСадердинов]

a = [i for i in a if a[i] != 0]
Да как это работаеееет

[makasin]

боже мой, не пишите так, куда легче prostata = lambda x: x>1 and all(x%i for i in range(2, int(x**0.5)+1)) всего 1 строчка, и забивать голову доп алгоритмами не нужно