Problem
Determine whether integer n is prime: it must be at least 2 and have exactly two positive divisors.
Worked examples
Input: n = 29
Output: true
No integer from 2 through 5 divides 29.
Hints
Hint 1
If a divisor exceeds the square root, its paired divisor is smaller than the square root.
Solution approach
- Reject values below 2. Check small factors first.
- Try divisors d while d × d ≤ n. Any exact divisor makes n composite.
- If none exists, return true. Use d ≤ n / d in fixed-width languages to avoid overflow.
Complexity
O(√n) time and O(1) space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗