Условие
A prime number is greater than 1 and divisible only by 1 and itself. Checking divisors up to the square root of n is enough.
Implement is_prime(n).
Input
n: The number to test.
Output
Return true if n is prime, otherwise false.
Ограничения
-1,000 ≤ n ≤ 1,000,000,000,000
Примеры
Пример 1
Ввод:
n = 29
Ожидаемый вывод:
expected = TrueВвод:
long long n = 29;
Ожидаемый вывод:
bool expected = true;Ввод:
long n = 29;
Ожидаемый вывод:
bool expected = true;Пояснение
29 has no divisors other than 1 and 29.
Пример 2
Ввод:
n = 21
Ожидаемый вывод:
expected = FalseВвод:
long long n = 21;
Ожидаемый вывод:
bool expected = false;Ввод:
long n = 21;
Ожидаемый вывод:
bool expected = false;Пояснение
21 = 3 × 7, so it is not prime.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Handle numbers below 2 first; they cannot be prime.
Подсказка 2
Test possible divisors only up to the square root of the number.
Подсказка 3
Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.
Ожидаемая сложность
O(sqrt(n)) time, O(1) extra space
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.