Foundations — Prime numbers — Sieve of Eratosthenes, primality testing

This page assumes nothing. Before we can even read the parent note, we need to agree on what each little symbol means and looks like. We build them in order — each one uses only the ones before it.

1. Natural numbers and the symbol $n$

Why a letter? Because we want to say something true for every counting number at once, without writing them all out. When we write $n$, picture a box holding one specific-but-unnamed number of pebbles.

2. Divides, factor, divisor — the heart of everything

This is the single most important idea, so we give it a picture.

Look at the figure. On the left, $12$ dots split cleanly into $3$ rows of $4$ — no dot is stranded. So $3\mid 12$ and $4\mid 12$. On the right, $12$ dots into rows of $5$ leaves a broken last row — $5$ does not divide $12$ (written $5\nmid 12$).

3. Building a number as a rectangle: $n=a\times b$

4. The inequality symbols $<$, $\le$, $>$, $\ge$

The parent note writes things like $1<d<n$ and $a\le b$. These are just size comparisons.

5. Square root ​ and why the topic loves it

The $\sqrt{n}$ trick is the parent's key optimisation, so we define  ​ from the rectangle idea.

6. The floor symbol $\lfloor \rfloor$

The parent writes $\lfloor \sqrt{n}\rfloor$. What is that odd bracket?

7. Big-O notation $O()$ — measuring effort

See Time complexity Big-O for the full story — here you only need "smaller inside the $O$ = less work."

8. Symbols summary table

Prerequisite map

Each foundation feeds exactly the part of the parent it unlocks: the rectangle picture powers the prime/composite split, the square root powers the $\sqrt{n}$ bound, floor makes it testable, and Big-O measures the payoff.

Equipment checklist

Self-test: can you answer each before revealing?

Connections

• Parent: Prime numbers & the Sieve
• Fundamental Theorem of Arithmetic
• Divisibility rules
• GCD and LCM
• Modular arithmetic
• Time complexity Big-O
• Factorisation