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

Описание задачи

Данная программа должна вывести все простые числа в заданном диапазоне (от 0 до n) при помощи алгоритма «Решето Эратосфена».

Решение задачи

1. Принимаем значение определяющее верхнюю границу диапазона и записываем его в переменную n.
2. Инициализируем переменную sieve («решето») множеством чисел от 2 до n.
3. Используем цикл while, который прекратит свою работу, когда множество sieve станет пустым.
4. Примем во внимание тот факт, что минимальное число в этом множестве (на первой итерации это будет 2) всегда простое.
5. Выводим это число на экран.
6. Далее удаляем это число вместе со всеми числами, кратными ему (в заданном диапазоне).
7. Продолжаем это делать, пока множество sieve не станет пустым.
8. Конец

Исходный код

Ниже дан исходный код для вывода всех простых чисел из заданного диапазона при помощи алгоритма под названием «решето Эратосфена». Результаты работы программы также даны ниже.

n = int(input("Введите верхнюю границу диапазона: "))
sieve = set(range(2, n+1))
while sieve:
    prime = min(sieve)
    print(prime, end = "\t")
    sieve -= set(range(prime, n+1, prime))

Объяснение работы программы

1. Пользователь вводит верхнюю границу диапазона, и она записывается в переменную n.
2. Инициализируем переменную sieve множеством всех чисел в диапазоне от 2 до n. Тип «множество» задается функцией set, а все числа диапазона определяются при помощи функции range.
3. Цикл while будет работать, пока множество sieve не станет пустым.
4. Переменная prime инициализируется минимальным значением из множества sieve. Обращаем внимание, что это всегда будет простое число. И это простое число выводится на экран.
5. Затем это число и все числа, кратные ему, удаляются из множества sieve.
6. Пункты 4 и 5 повторяются до тех пор, пока множество sieve не станет пустым, то есть количество элементов в нем станет равно 0.

Результаты работы программы

Пример 1:
Введите верхнюю границу диапазона: 10
2	3	5	7	
 
Пример 2:
Введите верхнюю границу диапазона: 15
2	3	5	7	11	13