Простое число — это число больше 1, которое делится только на 1 и само себя. Достаточно проверять делители до квадратного корня из n.
Реализуйте функцию is_prime(n).
Ввод
n: Число для проверки.
Вывод
Верните true, если n — простое, иначе false.
Ограничения
-1,000 ≤ n ≤ 1,000,000,000,000
Примеры
Ввод:
n = 29
Ожидаемый вывод:
expected = TrueВвод:
long long n = 29;
Ожидаемый вывод:
bool expected = true;Ввод:
long n = 29;
Ожидаемый вывод:
bool expected = true;Пояснение
У числа 29 нет делителей, кроме 1 и 29.
Ввод:
n = 21
Ожидаемый вывод:
expected = FalseВвод:
long long n = 21;
Ожидаемый вывод:
bool expected = false;Ввод:
long n = 21;
Ожидаемый вывод:
bool expected = false;Пояснение
21 = 3 × 7, поэтому оно не является простым.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Сначала обработайте числа меньше 2; они не могут быть простыми.
Подсказка 2
Проверяйте возможные делители только до квадратного корня числа.
Подсказка 3
Следите за чётными числами и повторяющимися множителями: одного делителя достаточно, чтобы число было не простым.
Ожидаемая сложность
время O(sqrt(n)), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.