DSA problem
Check if a Number is Prime
Given an integer N, determine whether it is a prime number. A prime is an integer greater than 1 whose only divisors are 1 and itself.
The brute-force check tests every candidate divisor from 2 to N - 1, but you only need to test up to the square root of N. If N had a factor larger than its square root, it would also have a matching factor smaller than the square root, since divisors come in pairs whose product is N. This sqrt(N) optimization recurs across divisor and factorization problems.
A further speed-up relies on the fact that every prime greater than 3 has the form 6k +/- 1. After ruling out multiples of 2 and 3, you can step through candidates in increments of 6, checking i and i + 2 each time. Remember the edge cases: 0 and 1 are not prime, and 2 is the only even prime.
Examples
N = 29trueN = 15falseConstraints
- 0 <= N <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.