Решето Эратосфена в Python

Введение

В ходе статьи используя алгоритм «Решето Эратосфена» найдём все простые числа до заданного числа N в Python.

Решето Эратосфена — это алгоритм нахождения всех простых чисел в диапазоне от 0, до заданного числа N.

Написание кода

Для начала дадим пользователю возможность ввода числа верхней границы диапазона:

n = int(input('Введите N: '))

Используя генератор заполним список значениями от одного, до заданного числа N:

n = int(input('Введите N: '))

a = [i for i in range(n + 1)]

Так как единица не является простым числом, заменим её на ноль:

n = int(input('Введите N: '))
a = [i for i in range(n + 1)]

a[1] = 0

Создадим переменную i равную двум, чтобы начать сразу с третьего элемента:

n = int(input('Введите N: '))
a = [i for i in range(n + 1)]

a[1] = 0

i = 2

Создадим цикл, который не закончится, пока i <= n. Внутри цикла зададим условие, что если значение ячейки ранее не было обнулено, то в ней хранится простое число. Первое кратное ему число будет больше в два раза:

n = int(input('Введите N: '))
a = [i for i in range(n + 1)]

a[1] = 0

i = 2
while i <= n:
    if a[i] != 0:
        j = i + i

Далее внутри условия создадим ещё один цикл while, который не закончится, пока j <= n. Мы выявили, что данное число является составным, поэтому заменяем его нулём. Прибавляем i к j:

n = int(input('Введите N: '))
a = [i for i in range(n + 1)]

a[1] = 0

i = 2
while i <= n:
    if a[i] != 0:
        j = i + i
        while j <= n :
            a[j] = 0
            j = j + i
    i += 1

Преобразуем список в множество, после чего удалим все нули и выведем его:

n = int(input('Введите N: '))
a = [i for i in range(n + 1)]

a[1] = 0

i = 2
while i <= n:
    if a[i] != 0:
        j = i + i
        while j <= n :
            a[j] = 0
            j = j + i
    i += 1

a = set(a)
a.remove(0)

print(a)

# Введите число N: 10
# {2, 3, 5, 7}

Заключение

В ходе статьи мы с Вами научились использовать алгоритм «Решето Эратосфена» для нахождения всех простых чисел в заданном диапазоне и написали код на Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂