Procedure

Primality by trial division up to $n$

Arithmetic • Number System • Prime Numbers

Statement

An integer

n > 1

is prime if and only if no prime

p

with

p^{2} \leq n

divides it. The bound is forced: if

n = ab

with

1 < a \leq b

, then

a^{2} \leq ab = n

, so every composite

n

has a prime factor not exceeding

n

How to use it

1Find the largest integer whose square does not exceed $n$ , then test only the primes up to it.
2Work upwards through $2, 3, 5, 7, 11, \dots$ and stop at the first divisor: it settles the matter as composite.
3For any $n < 121$ the only tests needed are $2, 3, 5, 7$ , because $1 1^{2} = 121$ .

211

prime?

Step-by-step

1
$1 4^{2} = 196 \leq 211 < 225 = 1 5^{2}$ , so test the primes $2, 3, 5, 7, 11, 13$
Why: Only a prime factor at or below $211$ could exist, and $211$ lies between $14$ and $15$ .
2
$211$ is odd; $2 + 1 + 1 = 4$ ; it does not end in $0$ or $5$ ; $211 = 7 (30) + 1 = 11 (19) + 2 = 13 (16) + 3$
Why: Each test is a divisibility rule or one short division, and none leaves remainder $0$ .
3
No prime up to $13$ divides $211$ , so $211$ is prime

Answer

Yes,

211

is prime

Watch out

The bound applies to PRIME divisors: testing composite divisors is wasted work, and stopping below

n

proves nothing at all. Testing every integer up to

\frac{n}{2}

is correct but far slower, and under time pressure that difference is the whole point.

Builds on

1

Also known as

trial division, primality test, test divisors up to the square root, is n prime, square root bound on a factor, check for primality