AlgoVerse

Primality test (trial division)

Divide n by 2, 3, … up to √n; if none of them divides n, n is prime.

If n = a·b and both factors were larger than √n, their product would exceed n. So every composite number has a divisor ≤ √n, and it is enough to try d = 2, 3, … while d·d ≤ n.

Read the full explanation ↓
Input:
n=97PDF export

97 is prime: only 2 to 9 are tried, because 10 × 10 is more than 97.

  1. def is_prime(n):
  2. if n < 2:
  3. return False
  4. d = 2
  5. while d * d <= n:
  6. if n % d == 0:
  7. return False
  8. d = d + 1
  9. return True

Invariant: No number from 2 to d − 1 divides n.

Start

n97
d—

Local variables

n97

Orange = changed in this step

Call stack

  1. is_prime()line 1
Step 1 of 29
Black = try_divisor · Orange = key steptry_divisor: 0/8 · prime: 0/1
    Explanation

    The idea

    If n = a·b and both factors were larger than √n, their product would exceed n. So every composite number has a divisor ≤ √n, and it is enough to try d = 2, 3, … while d·d ≤ n.

    Cost

    At most √n divisions. For numbers with hundreds of digits (like RSA keys) that is far too slow, and probabilistic tests such as Miller–Rabin are used instead.

    What to watch in the trace

    • The d card is the current divisor; see where the work stops.
    • "The square of a prime" shows why the condition is ≤.