Check for Prime Number
EasyTrial division up to the square root
Problem
A prime number has exactly two divisors: 1 and itself. Return whether n is prime.
A prime has exactly two factors: 1 and itself — check nothing in between divides it.
The idea
If n has a divisor larger than √n it must also have the paired one below √n, so testing divisors only up to √n is enough to be sure. That turns an O(n) scan into O(√n).
The trick
- Handle n < 2 first — 0 and 1 are not prime.
- After ruling out 2, you only need to test odd divisors.
- For many queries, sieve once up to the maximum instead of testing each number.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — n = 13 Values: 13.
1if n < 2: return false2for i in 2..sqrt(n):3 if n % i == 0: return false4return trueInput
- array
- [13]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 7
- Output:
- true
- Explanation:
- 7 has no divisors other than 1 and 7.
Example 2
- Input:
- n = 12
- Output:
- false
- Explanation:
- 12 = 3 x 4, so it has extra divisors.
Example 3
- Input:
- n = 1
- Output:
- false
- Explanation:
- 1 is not considered prime.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.