1835. Prime Verdict
by Rohit Parihar1 submission
A security desk accepts a ticket only if its number is prime, and it has to give an answer for each number it reads. Given the integer n, return true if n is a prime number and false otherwise. A prime has exactly two positive divisors, 1 and itself, so 0 and 1 are not prime.
The numbers can be as large as 10^12, so testing every smaller number as a divisor is too slow. It is enough to test divisors up to the square root of n, and after ruling out 2 you only need to test odd divisors. Aim for O(sqrt n) time and O(1) extra space.
Example 1
- Input:
- n = 29
- Output:
- true
- Explanation:
No number from 2 to 5 divides 29, so it is prime.
Example 2
- Input:
- n = 1
- Output:
- false
- Explanation:
1 has only one divisor, so it is not prime.
Example 3
- Input:
- n = 999999999989
- Output:
- true
- Explanation:
It has no divisor up to its square root, which is below 10^6, so it is prime.
Constraints
0 ≤ n ≤ 1012
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(sqrt n)
- Space
- O(1)