Primality Test
Medium · rating 1200 · Number Theory, Math
Read an integer n. Print YES if it is prime, otherwise NO.
Constraints: 1 ≤ n ≤ 109
Editorial
Primality Test is a classic number-theory interview question: determine whether an integer n is prime.
Approach
Numbers below 2 aren't prime. Otherwise test divisibility only up to √n — a factor larger than the square root would force a matching factor smaller than it, which you'd already have found. Skipping even candidates after 2 halves the work.
if n < 2: return False
if n % 2 == 0: return n == 2
i = 3
while i*i <= n:
if n % i == 0: return False
i += 2
return TrueComplexity
Time: O(√n). Space: O(1).
Related problems
- GCD of an Array — Medium
- Sum of Divisors — Medium
- Digit Sum in Base — Medium
- Greatest Common Divisor — Medium
- Modular Exponentiation — Medium
- Count Divisors — Easy