Создайте программу, которая проверяет, является ли натуральное число n, введенное с клавиатуры, простым числом

Тема: Проверка на простые числа

Описание:

Простые числа - это натуральные числа, которые имеют только два делителя: 1 и само число. Другими словами, простые числа не делятся ни на какие другие числа, кроме 1 и самого себя.

Чтобы проверить, является ли заданное натуральное число простым, мы можем применить следующий алгоритм:

1. Проверяем, является ли число n меньше или равным 1. Если да, то оно не является простым числом.
2. Иначе, делаем итерацию от 2 до корня из n и проверяем, делится ли n на любое из этих чисел без остатка. Если делится, то это число не является простым числом.
3. Если число не делится без остатка ни на одно из чисел от 2 до корня из n, то оно является простым числом.

Доп. материал:

Допустим, нам дано число n = 17. Мы применяем алгоритм:

1. Проверяем, меньше или равно ли n 1. Нет, поэтому продолжаем.
2. Делаем итерацию от 2 до корня из n (или до самого n). Проверяем делится ли n на 2 без остатка - нет. Затем проверяем делится ли n на 3 без остатка - нет. Затем проверяем делится ли n на 4 без остатка - нет. Продолжаем таким образом до 5, 6, ..., 16. Ни одно из этих чисел не является делителем n.
3. Поскольку n не делится без остатка ни на одно из чисел от 2 до 16, мы можем заключить, что n = 17 - простое число.

Совет:

Для более эффективной проверки простых чисел можно ограничить итерацию до корня из n, потому что делители числа всегда находятся в диапазоне от 2 до √n. Это помогает уменьшить количество операций и ускорить процесс проверки.

Упражнение:

Напишите программу на языке Python, которая принимает натуральное число от пользователя и проверяет, является ли оно простым числом.