Prime numbers — Sieve of Eratosthenes, primality testing: Worked examples

Before we start, one reminder of the notation we lean on, built from zero:

Definition The symbols we will use

$n$ ::: the natural number we are testing.
$p$ ::: a prime number (from the parent definition: $p > 1$ with only divisors $1$ and $p$ ). We reuse $p$ whenever we speak about a prime in general.
$k$ ::: a generic whole-number multiplier — a stand-in for "any integer", used when we write things like " $0 = 0 \times k$ ".
$⌊ x ⌋$ ::: the floor — "round down to the nearest whole number". Picture a number line; $⌊ 9.8 ⌋ = 9$ means "the last integer you pass on the way up to $9.8$ ".
$n$ ::: the side length of a square whose area is $n$ . If $n = a \times b$ is a rectangle, $n$ is the side of the square with the same area — and one of $a, b$ must be $\leq$ that side (the smaller-factor bound).
$d ∣ n$ ::: read " $d$ divides $n$ " — $n \div d$ leaves remainder $0$ .
$τ (n)$ ::: the divisor-count function — "how many positive whole numbers divide $n$ ". E.g. $τ (6) = 4$ because $1, 2, 3, 6$ all divide $6$ .

The scenario matrix

Every case this topic can throw at you falls into one of these cells. The worked examples below are tagged with the cell they cover, and together they hit all of them.

Cell	Case class	What makes it tricky	Example
A	Degenerate input: $n = 0$ or $n = 1$	Definition edge — "neither prime nor composite"	Ex 1
B	Smallest primes $n = 2, 3$	$⌊ n ⌋ < 2$ → no divisor to test	Ex 2
C	Genuine prime, mid-size	Must go all the way to $n$	Ex 3
D	Sneaky composite $p \times q$ , both odd	"Feels prime", small-prime tests miss it	Ex 4
E	Perfect square $= p^{2}$	The divisor sits exactly at $n$	Ex 5
F	Even / trivially composite	First test kills it	Ex 6
G	Full Sieve harvest up to $N$	Where to start/stop crossing	Ex 7
H	Real-world word problem	Translate → primality	Ex 8
I	Exam twist (count divisors / limiting)	Reason about structure, not brute force	Ex 9

Ex 1 — Cell A: the degenerate inputs $0$ and $1$

Worked example Is

$0$ prime? Is $1$ prime? Forecast: many students say "1 is prime, it's only divisible by itself." Pause and predict before reading.

Step 1 — Check the gate $n > 1$ . Why this step? The definition starts "a natural number greater than $1$ ". Both $0$ and $1$ fail this gate immediately.

$0$ : not $> 1$ . And $0 = 0 \times k$ for every whole-number multiplier $k$ — it has infinitely many divisors. Not prime, not composite.
$1$ : not $> 1$ . Its only divisor is $1$ itself — that is one divisor, but a prime needs exactly two distinct ( $1$ and the number itself).

Step 2 — Confirm via the "rectangle" picture. Why this step? A prime can only be a $1 \times p$ strip. $1$ is a single dot — not even a strip of length $\geq 2$ .

Verify: Both are neither prime nor composite. This is a convention, chosen so the Fundamental Theorem of Arithmetic stays clean: allowing $1$ would let $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$ , destroying uniqueness. ✓

Ex 2 — Cell B: the smallest primes $2$ and $3$

Ex 3 — Cell C: a genuine mid-size prime, $n = 149$

Worked example Is

$149$ prime? Forecast: it's odd, doesn't end in $5$ . Prime or hidden factor?

Step 1 — Bound. $149 \approx 12.2$ , so $⌊ 149 ⌋ = 12$ . Why this step? Any factor pair $a \times b$ has $a \leq 149 < 13$ , so we only need divisors up to $12$ .

Step 2 — Test only the primes up to $12$ : $2, 3, 5, 7, 11$ . Why only primes? By the shortcut in the notation box, a composite divisor (like $4, 6, 8, 9, 10$ ) would drag a smaller prime factor along, and we'd have caught that prime first. So primes alone cover every case. We use Divisibility rules to save arithmetic.

$2$ : $149$ is odd → no.
$3$ : digit sum $1 + 4 + 9 = 14$ , not a multiple of $3$ → no.
$5$ : ends in $9$ → no.
$7$ : $7 \times 21 = 147$ , remainder $2$ → no.
$11$ : alternating sum $1 - 4 + 9 = 6$ , not a multiple of $11$ → no.

Step 3 — Stop at $11$ . Why this step? Next prime is $13$ , and $13 > 12 = ⌊ 149 ⌋$ . A divisor $\geq 13$ would need a partner $\leq 149/13 \approx 11.5 < 13$ — which we already ruled out. So we're done.

Verify: No divisor $\leq 12$ . $149$ is prime. ✓

Ex 4 — Cell D: the sneaky composite $n = 221$

This is the trap the parent warned about, made concrete.

Figure — Prime numbers — Sieve of Eratosthenes, primality testing

The figure lays the candidate divisors $0$ – $20$ on a number line. The dashed plum line marks $221 \approx 14.9$ . The teal dot at $13$ is the smaller factor and the orange dot at $17$ is the larger factor — notice $13$ sits just left of the plum line and $17$ sits right of it. The arrow shows exactly where a rushed "gut" test stops (after $11$ ), one prime short of the divisor that would have unmasked $221$ . Keep that picture in mind as we walk the steps.

Worked example Is

$221$ prime? Forecast: odd, not divisible by $3$ (digit sum $5$ ) or $5$ . Gut says prime?

Step 1 — Bound. $221 \approx 14.9$ , so $⌊ 221 ⌋ = 14$ . Why this step? We must test primes up to $14$ : $2, 3, 5, 7, 11, 13$ .

Step 2 — Test the small ones (the ones the gut checks). Why only these primes? Same shortcut — composite divisors are covered by their prime factors. We reproduce the incomplete gut check to see where it stops.

$2$ : odd → no. $3$ : digit sum $5$ → no. $5$ : ends $1$ → no. $7$ : $7 \times 31 = 217$ , rem $4$ → no. $11$ : alternating sum $1 - 2 + 2 = 1$ , not a multiple of $11$ → no.

Step 3 — Do NOT stop. Test $13$ . Why this step? $13 \leq 14$ , so it's still in range (the teal dot in the figure) — this is the whole lesson. $13 \times 17 = 221$ . Found it.

Verify: $221 = 13 \times 17$ , composite. Sanity: $13 \times 17 = 221$ ✓. The factor pair is $(13, 17)$ — notice $13 < 221 < 17$ : the smaller factor really does sit below the square root, exactly as the bound promises. ✓

Ex 5 — Cell E: a perfect square, $n = 169$

Ex 6 — Cell F: trivially composite, $n = 150$

Ex 7 — Cell G: full Sieve harvest up to $N = 50$

The Sieve isn't a per-number test — it paints out whole arithmetic ladders at once. Watch each colour.

Worked example Find every prime

$\leq 50$ with the Sieve. Forecast: which primes $p$ do you actually need to sieve with? Guess before Step 1.

Step 1 — Bound the callers. $50 \approx 7.07$ , so we only sieve with primes $p \leq 7$ : that's $2, 3, 5, 7$ . Why this step? Any composite $\leq 50$ has a prime factor $\leq 50 < 8$ ; anything left un-crossed after $p = 7$ is automatically prime.

Step 2 — $p = 2$ , start at $2^{2} = 4$ . Why start at $4$ ? Every multiple of $2$ below $4$ (just $2$ ) is either prime itself or already handled. Cross $4, 6, 8, \dots, 50$ .

Step 3 — $p = 3$ , start at $3^{2} = 9$ . Why $9$ ? $2 \cdot 3 = 6$ was already crossed by $2$ ; the first new multiple of $3$ is $3 \cdot 3 = 9$ . Cross $9, 15, 21, 27, 33, 39, 45$ (evens like $12$ already gone).

Step 4 — $p = 5$ , start at $5^{2} = 25$ . Cross $25, 35, 45$ . ( $10, 15, 20$ already gone.)

Step 5 — $p = 7$ , start at $7^{2} = 49$ . Cross $49$ . Next prime is $11$ , but $1 1^{2} = 121 > 50$ → stop.

Verify: Survivors are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$ That's 15 primes below $50$ . Cross-check with the count of primes below $50$ (known value $15$ ). ✓

Ex 8 — Cell H: real-world word problem

Worked example The locker gears

Two gears mesh: one has $221$ teeth, the other $17$ . They start aligned. After how many teeth-steps do the same two teeth meet again — and is either tooth-count prime?

Forecast: you smell an LCM problem. But there's a primality catch.

Step 1 — Translate. Why this step? "Same two teeth realign" = smallest number that is a multiple of both counts = $lcm (221, 17)$ .

Step 2 — Test $17$ for primality. $17 \approx 4.1$ , test primes $2, 3$ : odd, digit sum $8$ → both fail. $17$ is prime.

Step 3 — Test/factor $221$ . From Ex 4, $221 = 13 \times 17$ . Why this matters? Because $17 ∣ 221$ , the two tooth-counts share the factor $17$ : $g cd (221, 17) = 17$ .

Step 4 — Compute the LCM. Why this formula? $lcm (a, b) = \frac{a \cdot b}{g cd ( a , b )}$ . $lcm (221, 17) = \frac{221 \times 17}{17} = 221.$

Verify: They realign after $221$ teeth-steps. Makes sense: since $17 ∣ 221$ , the small gear completes a whole number of turns ( $221/17 = 13$ ) exactly when the big gear completes $1$ turn. $17$ is prime; $221$ is composite. ✓

Ex 9 — Cell I: exam twist (count divisors without brute force)

Worked example How many positive divisors does

$360$ have — and why does that instantly tell you it is not prime? Forecast: guess the divisor count before computing.

Step 1 — Prime-factorise. Why this step? The Fundamental Theorem of Arithmetic says every number's divisor structure is fixed by its prime factorisation. $360 = 2^{3} \times 3^{2} \times 5^{1} .$

Step 2 — Apply the divisor-count formula. Why this formula? A divisor of $2^{3} 3^{2} 5^{1}$ is any $2^{a} 3^{b} 5^{c}$ with $0 \leq a \leq 3$ , $0 \leq b \leq 2$ , $0 \leq c \leq 1$ . The number of independent choices multiplies. Recall $τ (n)$ counts divisors: $τ (360) = (3 + 1) (2 + 1) (1 + 1) = 4 \times 3 \times 2 = 24.$

Step 3 — Read off the primality verdict. Why this step? A prime has exactly $2$ divisors. $360$ has $24$ — nowhere close. In general $τ (n) = 2 ⟺ n$ is prime.

Verify: $360$ has $24$ divisors; since $24 \neq = 2$ , it is composite. Spot-check the formula on a known prime: $τ (13) = τ (1 3^{1}) = 1 + 1 = 2$ ✓. ✓

Recall

Recall Which cell did each example patch?

$0$ and $1$ ::: Cell A — fail the $n > 1$ gate; neither prime nor composite.
$2, 3$ ::: Cell B — empty test range, auto-prime.
$149$ ::: Cell C — real prime, test primes up to $⌊ 149 ⌋ = 12$ .
$221$ ::: Cell D — $= 13 \times 17$ , the "don't stop early" trap.
$169$ ::: Cell E — $= 1 3^{2}$ , factor sits on $n$ ; use $\leq$ , not $<$ .
$150$ ::: Cell F — even, dies on first test.
Sieve to $50$ ::: Cell G — sieve with $2, 3, 5, 7$ only; $15$ primes.
Gears ::: Cell H — LCM $= 221$ because $17 ∣ 221$ .
$τ (360) = 24$ ::: Cell I — divisor formula; $\neq = 2$ so composite.

Connections

Prime numbers — Sieve of Eratosthenes, primality testing
Fundamental Theorem of Arithmetic
Divisibility rules
GCD and LCM
Factorisation
Time complexity Big-O