Проверка числа на простоту
💻 Информатика · 8 класс
Какое число называют простым
Простое число — это натуральное число больше единицы, которое делится без остатка только на 1 и на само себя. Например, 7 простое, потому что других делителей у него нет. Число, у которого есть и другие делители, называют составным (например, 12 делится на 2, 3, 4, 6). Единица не считается ни простым, ни составным числом — это особый случай, который надо запомнить.
Задача проверки числа на простоту — хороший пример использования цикла с проверкой условия и операции взятия остатка от деления. На ней удобно научиться организовывать перебор и применять логический признак-флаг.
Идея проверки перебором
Чтобы определить, простое ли число n, перебирают возможные делители от 2 до n − 1 и проверяют остаток от деления. Если хотя бы один делитель найден, число составное. Если ни один не подошёл — число простое. Признаком делимости служит нулевой остаток, который получают операцией взятия остатка.
Правило. Достаточно проверять делители до корня из n: если у числа есть делитель больше корня, то обязательно найдётся и парный ему делитель меньше корня. Это сильно ускоряет проверку больших чисел.
Разобранный пример
# Питон, проверка простоты числа n
n = 7
prostoe = True # пока считаем число простым
for d in range(2, n):
if n % d == 0: # нашли делитель
prostoe = False
if prostoe and n > 1:
print('простое')
else:
print('составное')Здесь n % d — это остаток от деления n на d. Как только он равен нулю, значит делитель найден, и флаг prostoe становится ложным. Переменная-флаг хранит логическое значение и удобно показывает итог проверки.
Как работает перебор для числа 7
Проследим проверку делителей числа 7 по шагам.
| Делитель d | Остаток 7 % d | Делится? |
|---|---|---|
| 2 | 1 | нет |
| 3 | 1 | нет |
| 4 | 3 | нет |
| 5 | 2 | нет |
| 6 | 1 | нет |
Ни один делитель не подошёл, поэтому флаг остался истинным, и число 7 признано простым.
Примеры чисел
| Число | Делители | Вид |
|---|---|---|
| 2 | 1, 2 | простое |
| 9 | 1, 3, 9 | составное |
| 11 | 1, 11 | простое |
| 15 | 1, 3, 5, 15 | составное |
Досрочный выход из перебора
В приведённой программе цикл проходит все делители до конца, даже если делитель уже найден. Это лишняя работа. На практике, как только обнаружен первый делитель, проверку можно прекратить — число уже точно составное. Для досрочного выхода используют специальный оператор прерывания цикла, что заметно ускоряет программу для больших составных чисел.
Частая ошибка. Забывают про условие n > 1. Без него единица ошибочно попадёт в простые числа, хотя по определению таковым не является. Также иногда начинают перебор с единицы, но деление на единицу есть всегда, поэтому делители начинают проверять с двойки.Кратко о главном
- Простое число делится только на
1и на само себя. - Проверку выполняют перебором делителей и проверкой остатка.
- Нулевой остаток означает, что делитель найден и число составное.
- Достаточно проверять делители до корня из числа.
- Единица не относится ни к простым, ни к составным числам.