Проверка простоты числа перебором делителей. Решение задачи на Python
Пользователь вводит натуральное число больше единицы. Надо определить, простое оно или сложное.
Поскольку надо вывести только одно из этих сообщений, либо то, либо другое, понадобится условный оператор.
Если число простое, то выведем такую надпись. Иначе, то есть когда число сложное, выведем другую.
Переменной simple присвоим истину, то есть изначально будем предполагать, что было введено простое число.
Если в процессе проверки окажется, что число сложное, то значение simple поменяем на False, то есть ложь.
Тестировать на простоту будем методом перебора делителей. Это значит, надо проверять делится ли заданное число нацело на натуральные числа, которые ему предшествуют. И эти предшествующие числа будем перебирать друг за другом, начиная с двойки.
Перебирать их будем в цикле, постепенно увеличивая i.
В теле цикла надо узнавать, делится ли число n на текущее значение i. В таком случае остаток от деления будет равен нулю. Знак процента в Python – это нахождение остатка от деления.
Если это так, то число не может быть простым. Потому что простые числа делятся только на единицу и самих себя. А мы перебираем i от двух до числа меньше чем n.
Чтобы обозначить, что число сложное, присваиваем simple значение False.
Смотрим, как работает программа. Вводим простое число, теперь сложное.
Но давайте посмотрим, как много раз выполняется тело цикла и с каким значением simple заходит в него.
Уже при заходе на вторую итерацию переменная simple имела значение False. И в этой и в последующих итерациях смысла нет. Потому что 12 нацело делится на два, и дальше проверять натуральные числа уже нет необходимости.
Можно прервать выполнение цикла, поместив в его тело оператор break.
Теперь, как только будет обнаружен делитель, поменяется не только значение simple, но и произойдет выход из цикла.
Однако мы избегаем лишних итераций цикла лишь в том случае, если вводится сложное число.
Если же простое, в if поток выполнения никогда не заходит.
Но надо ли пытаться делить число на все предшествующие ему числа?
Смотрите, если заданное число делилось бы на число в середине ряда, то вторым его делителем была бы двойка. Но если мы переходим середину, то второй делитель должен быть меньше двойки, а этого быть не может. Значит, как минимум перебирать числа надо не до n, а до n деленного на 2.
Но и это еще не всё. Если мы имеем дело со сложным числом, то оно как и простое делится на себя и единицу. Однако кроме этого имеет и другие делители. И эти другие делители появляются не по одному, а парами. То есть если, например, число делится на 2, то будет еще какой-то делитель, который при умножении на 2 даст нам заданное число.
Чем больше больший делитель, тем меньше меньший делитель.
Если мы берем самый большой из меньших делителей, то его парой будет самый маленький делитель из больших.
Но есть граница, когда оба делителя могут быть равны, – это квадратный корень из исследуемого числа. Можно сказать, он является максимально возможным делителем в ряду меньших делителей.
Поэтому если мы не находим делитель до квадратного корня включительно, значит у числа их вообще нет, и оно простое.
Это работает и для простых чисел. Фактически нам здесь надо перебирать только до четырех. Потому что четыре в квадрате – это 16. А 5 в квадрате – уже 25, это больше семнадцати.
Поэтому в условии цикла мы можем извлечь квадратный корень из n.
Текстовое описание решения задачи и исходный код программы: https://younglinux.info/algorithm/div...
Больше задач: https://younglinux.info/python/task
Приложение для андроид: https://play.google.com/store/apps/de...
Купить PDF-версию (100 задач): https://younglinux.info/store/store.h...
Смотрите видео Проверка простоты числа перебором делителей. Решение задачи на Python онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Лаборатория линуксоида 27 Декабрь 2021, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 12,56 раз и оно понравилось 14 людям.