Visual walkthrough — Prime numbers — Sieve of Eratosthenes, primality testing

We build everything from one single idea: a number is a pile of dots, and multiplication is arranging those dots into a rectangle.

---

Step 1 — What a number looks like (dots in a row)

WHAT. Forget symbols. A whole number is just a count of identical dots. The number $7$ is seven dots. Nothing more.

WHY. Every later argument is about splitting a number. Before we can split, we must picture the thing being split. Dots are the most honest picture — they don't hide any structure.

PICTURE. Look at the figure. On top, $7$ dots sit in a single straight line. Below, $12$ dots also start as a line. So far they look the same — both are "just a row."

The question that drives this whole page: can these dots be re-arranged into a filled rectangle wider than one dot?

---

Step 2 — Multiplication is a rectangle, factors are its sides

WHAT. Take $n$ dots and try to line them up in a filled rectangle: $a$ rows of $b$ dots each. If it works with no gaps, then $n=a\times b$.

WHY. This turns the abstract idea "divides evenly" into something your eyes can check: does the rectangle come out perfectly full, or is there a ragged leftover? A ragged leftover means $a$ does not divide $n$.

PICTURE. $12$ dots snap neatly into a $3\times 4$ block — no gaps. That is a factorisation. The two numbers on the sides are its factors.

This is exactly the parent's "you cannot split it into a rectangle wider than 1," drawn out.

---

Step 3 — The prime has only the flat rectangle (and where 1 stands)

WHAT. Try to force $7$ dots into a block with $2$ or more rows. Every attempt leaves a ragged last row. Then look at the smallest pile of all — a single dot, $1$.

WHY. This is what "prime" feels like from the inside. It is not a mystical property — it is the plain fact that $7$ dots refuse to tile any rectangle except the flat $1\times 7$. And the number $1$ is a special case we must settle before building anything.

PICTURE. Rows of $2$: last row half-empty. Rows of $3$: last row has one dot. There is no clean block. Only the single line survives. Off to the side sits the lone dot $1$ — it has no "second rectangle" and no genuine flat line either.

---

Step 4 — The key insight: one side of the rectangle is always short

WHAT. Take any composite number and its block $n=a\times b$. Rename the sides so that $a$ is the smaller (or equal) side: $a\le b$ (recall $\le$ from the opening definition — "$a$ is not to the right of $b$"). Now watch the shape.

WHY. Testing every possible divisor is slow. If we can prove the short side can never be very long, we only have to check small divisors — and we'll have covered every rectangle automatically. This is the entire reason we care about the shape.

PICTURE. A wide-but-short rectangle: many columns, few rows. Overlay the biggest square that fits ($a\times a$). The square sits inside the rectangle — it cannot poke past it, because the rectangle is at least as wide as it is tall.

Take the square root of both sides (the square root just asks "what side length gives this area?"):

$a^2\le n⟹a\le \sqrt{n}$

Conclusion of the step: the smaller side $a$ of any rectangle is at most $\sqrt{n}$. So if there is no divisor $\le \sqrt{n}$, there is no rectangle at all — the number is prime.

---

Step 5 — Trial division, drawn as a search up to $\sqrt{n}$

WHAT. To test whether $n$ is prime, try each candidate short side $d=2,3,4,\dots ,\lfloor \sqrt{n}\rfloor$. If none tiles a clean rectangle, $n$ is prime.

WHY. Step 4 promised the short side never exceeds $\sqrt{n}$. So the search window $[2,\sqrt{n}]$ is guaranteed complete — we cannot miss a factor by stopping there. Going further would only re-find the tall partner of a short side we already tested.

PICTURE. A number line from $2$ to $n$. A shaded band covers $2$ to $\lfloor \sqrt{n}\rfloor$ — "the only place a short side can live." Everything to the right of $\sqrt{n}$ is the partner zone; it is checked for free.

This shrinks the work from $O(n)$ to $O(\sqrt{n})$ — see Time complexity Big-O. For $n=97$: $\sqrt{97}\approx 9.8$, so we test only $2,3,5,7$ and finish in four checks.

---

Step 6 — The Sieve: kill whole rectangles at once

WHAT. First, fix a ceiling. Let $N$ be the largest number we want to test — we will find every prime from $2$ up to this $N$. Now lay out all of $2,3,\dots ,N$ and cross off every multiple of $2$, then of $3$, then of $5$, and so on. A crossed number is "some rectangle's area" — a composite. Survivors are prime.

WHY. Trial division re-checks $2$ against every number separately. That repeats work. The sieve does the reverse: pick a short side $p$ once, and knock out all numbers that have $p$ as a factor in a single sweep.

PICTURE. The grid $1\dots N$ with $N=30$. The $p=2$ sweep paints all even numbers. Follow the arrow jumping $+2$ each time: $4,6,8,\dots$ — every one is a rectangle "$2\times$ something."

---

Step 7 — Why crossing starts at $p^2$, not $2p$

WHAT. When we sweep prime $p$, we begin crossing at $p^2$, skipping the earlier multiples $2p,3p,\dots ,(p-1)p$. Here the multiplier is a whole number $k$ ranging over the integers $2,3,\dots ,p-1$; the multiple we skip is $k\cdot p$.

WHY. Every skipped multiple $k\cdot p$ with $k<p$ has a factor $k$ smaller than $p$. That means it was already crossed during the earlier sweep of $k$'s smallest prime. The first new victim is $p\cdot p=p^2$ (this is $k\cdot p$ with $k=p$), where both sides are $\ge p$.

PICTURE. The multiples of $5$: $10,15,20$ are already faded (killed by $2$, $3$, $2$). The first fresh cross lands on $25=5\times 5$. The green arrow points at $p^2$ as the true starting gun.

---

Step 8 — Why we stop when $p^2>N$ (and what happens to 1)

WHAT. Once the current prime $p$ satisfies $p^2>N$, we stop sieving. Every number from $2$ still standing is declared prime. The lone cell $1$ needs a separate ruling — see below.

WHY. By Step 4, every composite $\le N$ has a short side $\le \sqrt{N}$, hence a prime short side $\le \sqrt{N}$. So every composite was crossed during a sweep with some $p\le \sqrt{N}$. Once $p>\sqrt{N}$ (equivalently $p^2>N$), no un-crossed composite can remain — anything still standing has no short side, so it is prime.

PICTURE. The finished $1\dots 30$ grid. Sieved with $p=2,3,5$ only ($7^2=49>30$). Crossed cells are pale; the survivors $2,3,5,7,11,13,17,19,23,29$ glow. The cell $1$ is shaded a third colour — a reminder it is not a prime even though nothing crossed it. The dashed line marks $\sqrt{30}\approx 5.5$ — the "no need to sieve past here" wall.

---

The one-picture summary

The final figure is not a restatement — it is the decision tree a computer (or you) actually runs on a single number $n$, with every branch from this page wired in: the $\le \sqrt{n}$ window, the $p^2$ start, the $\sqrt{N}$ stop, and the two special exits for $1$ and the primes.

Recall Feynman: tell it back in plain words

Every number is a pile of dots. A dot-pile is composite when the dots snap into a real rectangle — rows and columns both bigger than one. The number $1$ is a single dot: it makes no rectangle and no genuine flat line, so it is neither prime nor composite — a special leftover we set aside by hand. Now here is the trick that runs everything: line any rectangle up so its short side is on the left. That short side can never be longer than the number's square root — because if both sides were long, the block would hold more dots than we started with. So to check if a number is prime, I only walk the divisors up to its square root; if none makes a clean rectangle, no rectangle exists and it's prime. The sieve does this for a whole crowd from $2$ up to my ceiling $N$: the number $2$ shouts "sit down!" to all its multiples, then $3$, then $5$. But each caller $p$ starts shouting from its own square $p^2$, because the smaller multiples $k\cdot p$ (with the counter $k$ below $p$) were already told to sit by smaller callers. And I only need callers up to the square root of $N$ — after that, everyone still standing (except the odd-one-out $1$) could never form a rectangle, so they must be prime.

---

Connections

• Prime numbers — Sieve of Eratosthenes, primality testing (parent)
• Factorisation
• Divisibility rules
• Modular arithmetic
• Time complexity Big-O
• Fundamental Theorem of Arithmetic
• GCD and LCM