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 True

Complexity

Time: O(√n). Space: O(1).

Open Primality Test in Code Arena →