Является ли число простым и сколько у него делителей.
Простое число — это натуральное число больше 1, которое делится только на 1 и на само себя. Первые из них: 2, 3, 5, 7, 11 и 13. Двойка — единственное чётное простое число, поскольку любое другое чётное делится на 2 и потому составное.
Это выбор определения, у которого есть практическая причина. Основная теорема арифметики утверждает, что каждое число раскладывается на простые множители единственным образом. Если бы 1 считалась простой, разложений было бы бесконечно много, ведь единицы можно домножать сколько угодно. Исключение единицы сохраняет теорему.
Достаточно проверить делимость на все простые числа до квадратного корня из данного числа. Для 97 корень примерно 9,8, поэтому достаточно проверить 2, 3, 5 и 7 — ни одно не делит, значит 97 простое. Дальше проверять бессмысленно: больший делитель потребовал бы меньшего парного, который уже был бы найден.
Бесконечно много — это доказал Евклид более двух тысяч лет назад. Доказательство короткое: если бы простых чисел было конечное число, их можно было бы все перемножить и прибавить единицу, получив число, не делящееся ни на одно из них. Чем дальше по числовой оси, тем реже встречаются простые, но они никогда не кончаются.