Простым числом называется натуральное число большее единицы и делящееся только на единицу и на само себя.
Вот первые простые числа: 2 3 5 7 11 13 17 …
Напишем программу на Питоне, которая вычисляет и печатает все простые числа от 1 до 1000.
Так как 1 не является простым, что его брать? Будем брать с «двойки» и испытывать её, затем 3 и испытывать её, 4 и так далее… Мы видим – идёт повторение «брать», значит, надо открыть цикл for по числу n = 2, 3, 4, … :
for n in range(2, 1001):
Почему c 2 – понятно. Почему до 1001? Потому что Питон – это дурацкий язык. По его правилам for топает до числа на единицу меньше, чем последнее. То есть пишется 1001, но оно не берётся, а берётся 1000 последним.
Вот взяли мы число n. Его делители 1 и n – не в счёт. Сначала будем думать, что у него нет других делителей. То есть количество других делителей – ноль. Количество других делителей испытываемого числа n будем хранить в ячейке k:
k = 0
Начинаем перебирать кандидатов d в делители по порядку, начиная с 2 и кончая корнем квадратным из n:
for d in range(2, int(n ** 0.5) + 1):
Корень квадратный из n написан как n ** 0,5, так как извлечение квадратного корня равносильно возведению в степень 0,5. Число n ** 0,5 в Питоне не будет целым даже если в математике n ** 0,5 является целым. Поэтому приделан оператор взятия целой части: int(n ** 0.5). Единица прибавлена потому, что, как мы уже знаем, for не дотопает до корня из n, а остановится на единицу меньше. А нам нужно, чтобы кандидат d принял значение корня из n. Поэтому for идёт до int(n ** 0.5) + 1.
Почему кандидаты d перебираются до корня из n? Это сделано для ускорения работы программы, так как нет смысла испытывать в качестве кандидатов бОльшие числа.
Итак, начали перебирать кандидатов в делители:
for d in range(2, int(n ** 0.5) + 1):
Рассуждаем так: если n делится нацело на d, значит, нашёлся делитель. А как записать «n делится нацело на d»? Это значит остаток от деления n на d равен 0: n % d == 0. А почему два знака равенства? Потому что Питон – дурацкий язык, в проверке условия пишется «два равна», для хранения в ячейке – «одно равно». Что же вырисовывается:
for n in range(2, 1001): # берём число n
k = 0 # пусть число делителей у n равно 0
for d in range(2, int(n ** 0.5) + 1): # перебираем кандидатов в делители
if n % d == 0: # если n делится нацело на d, то
k = 1 # нашёлся делитель
Если нашёлся делитель – значит, число n непростое и перебор новых кандидатов d в делители стоит прекратить:
break
И брать следующее n.
А если весь цикл по d пройдёт, и n ни разу не разделится нацело на d, значит, k останется равным нулю.
А вот если k останется равным нулю, значит, n – число простое и его надо напечатать. Это будет выглядеть так:
if k == 0: print(n, end = ’ ‘)
Можно было бы написать просто print(n), но тогда простые числа будут печататься на мониторе вертикально в столбик, что неудобно, а end = ’ ‘ обеспечит нам печать в строчку да ещё и с промежутками ’ ‘.
И берём следующее n.
Значит, в любом случае берём следующее n, очищая ячейку k во второй строке программы.
Что же получилось? Вот полный текст программы:
Цикл по d для n = 2 просто не работает.
Программа маленькая, недолго будет набрать её самостоятельно в редакторе Питона. Тем более, что написанное после символа # и сам символ # можно не набирать. Писать текст программы в этой статье – неблагодарное дело. Текст будет искажён уничтожением отступов. А Питон чётко требует наличие отступов в нужных местах. Если их не будет, программа работать не будет. Отступы – увы – это ещё одна из многих дуростей Питона. Но что делать? Поэтому не сочтите за труд, наберите самостоятельно текст по приводимой фотографии в точности, соблюдая все отступы. Иначе всё повествование пойдёт насмарку.
После запуска программа выдаст результат – простые числа от 1 до 1000:
Конечно, для решения поставленной задачи можно написать программу по-другому. Можно попробовать написать программу, которая будет работать быстрее.
Успехов Вам в программировании!