Problem
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.
Constraints
-1,000 ≤ n ≤ 1,000,000,000,000
Examples
Example 1
Input:
n = 29
Expected output:
expected = TrueInput:
long long n = 29;
Expected output:
bool expected = true;Input:
long n = 29;
Expected output:
bool expected = true;Explanation
29 has no divisors other than 1 and 29.
Example 2
Input:
n = 21
Expected output:
expected = FalseInput:
long long n = 21;
Expected output:
bool expected = false;Input:
long n = 21;
Expected output:
bool expected = false;Explanation
21 = 3 × 7, so it is not prime.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Handle numbers below 2 first; they cannot be prime.
Hint 2
Test possible divisors only up to the square root of the number.
Hint 3
Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.
Expected complexity
O(sqrt(n)) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.