Intuition The one-sentence ideaA prime is a number with no "hidden factors" — you cannot split it into a rectangle of dots wider than 1. The Sieve removes every number that IS a rectangle, so whatever survives must be prime.
Definition Prime & compositeA natural number p > 1 p > 1 p > 1 prime if its only positive divisors are = = 1 = = ==1== == 1 == = = p = = ==p== == p == n > 1 n>1 n > 1 not prime is composite (it has a divisor d d d 1 < d < n 1 < d < n 1 < d < n = = 1 = = ==1== == 1 ==
Intuition WHY is 1 excluded?If we allowed 1 to be prime, then 12 = 2 ⋅ 2 ⋅ 3 = 1 ⋅ 2 ⋅ 2 ⋅ 3 = 1 ⋅ 1 ⋅ 2 ⋅ 2 ⋅ 3 … 12 = 2\cdot2\cdot3 = 1\cdot2\cdot2\cdot3 = 1\cdot1\cdot2\cdot2\cdot3\dots 12 = 2 ⋅ 2 ⋅ 3 = 1 ⋅ 2 ⋅ 2 ⋅ 3 = 1 ⋅ 1 ⋅ 2 ⋅ 2 ⋅ 3 … unique . Excluding 1 keeps the Fundamental Theorem of Arithmetic ("every integer factors into primes in exactly one way") clean.
Goal: decide if n n n
Naive: test every d d d 2 2 2 n − 1 n-1 n − 1 n n n
The key optimisation — why n \sqrt{n} n
Suppose n n n n = a × b n = a \times b n = a × b 1 < a ≤ b < n 1 < a \le b < n 1 < a ≤ b < n
So the test becomes:
check d = 2 , 3 , 4 , … , ⌊ n ⌋ \text{check } d = 2, 3, 4, \dots, \lfloor\sqrt{n}\rfloor check d = 2 , 3 , 4 , … , ⌊ n ⌋
Cost drops from O ( n ) O(n) O ( n ) O ( n ) O(\sqrt n) O ( n )
Worked example Is 97 prime? — Forecast-then-VerifyForecast: 97 looks prime.
97 ≈ 9.8 \sqrt{97} \approx 9.8 97 ≈ 9.8 d = 2 , 3 , 5 , 7 d = 2,3,5,7 d = 2 , 3 , 5 , 7
97 / 2 97/2 97/2 Why this step? Even divisor test.97 / 3 97/3 97/3 3 ⋅ 32 = 96 3\cdot32=96 3 ⋅ 32 = 96 97 / 5 97/5 97/5 97 / 7 97/7 97/7 7 ⋅ 13 = 91 7\cdot13=91 7 ⋅ 13 = 91 ≤ 9 \le 9 ≤ 9 Verify: 97 is prime. ✓
Worked example Is 91 prime? (steel-man your intuition)Forecast: "91 is odd, not divisible by 3 or 5 — feels prime."
91 ≈ 9.5 \sqrt{91}\approx 9.5 91 ≈ 9.5
7 × 13 = 91 7 \times 13 = 91 7 × 13 = 91 Why this step? We must go all the way to n \sqrt n n Verify: 91 = 7×13, composite. The gut-feeling was wrong precisely because we forgot 7.
Idea: Instead of testing numbers one-by-one, cross out all multiples of each prime. What remains is prime.
Intuition WHY start crossing atp 2 p^2 p 2 2 p 2p 2 p k ⋅ p k\cdot p k ⋅ p k < p k < p k < p already crossed when we sieved the smaller prime k k k 2 ⋅ 5 = 10 2\cdot5=10 2 ⋅ 5 = 10 first new multiple is p ⋅ p p\cdot p p ⋅ p
p 2 > N p^2 > N p 2 > N n \sqrt n n ≤ N \le N ≤ N ≤ N \le \sqrt N ≤ N p > N p > \sqrt N p > N
Worked example Sieve up toN = 30 N=30 N = 30 30 ≈ 5.5 \sqrt{30}\approx5.5 30 ≈ 5.5 p = 2 , 3 , 5 p=2,3,5 p = 2 , 3 , 5
p = 2 p=2 p = 2 4 , 6 , 8 , … , 30 4,6,8,\dots,30 4 , 6 , 8 , … , 30 Why: remove all evens ≥ 4 \ge 4 ≥ 4 p = 3 p=3 p = 3 9 9 9 9 , 12 , 15 , 18 , 21 , 24 , 27 , 30 9,12,15,18,21,24,27,30 9 , 12 , 15 , 18 , 21 , 24 , 27 , 30 p = 5 p=5 p = 5 25 25 25 25 , 30 25,30 25 , 30 p = 7 p=7 p = 7 7 2 = 49 > 30 7^2=49>30 7 2 = 49 > 30 stop .
Survivors: 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 \boxed{2,3,5,7,11,13,17,19,23,29} 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29
Common mistake "1 is prime because it's only divisible by 1 and itself."Why it feels right: it fits the words of the definition loosely.
Fix: the definition requires exactly two distinct divisors. 1 has only one divisor (1=itself). Also, allowing it breaks unique factorisation.
Common mistake "Stop trial division early once no small factor is found."Why it feels right: small primes catch most composites, so it usually works.
Fix: you must go to ⌊ n ⌋ \lfloor\sqrt n\rfloor ⌊ n ⌋ 91 = 7 × 13 91=7\times13 91 = 7 × 13 221 = 13 × 17 221=13\times17 221 = 13 × 17
Common mistake "Sieve: cross out multiples starting from2 p 2p 2 p Why it feels right: 2 p 2p 2 p p p p Fix: correct but wasteful; those below p 2 p^2 p 2 p 2 p^2 p 2
Common mistake "In the sieve, keep sieving with every prime up to N."Why it feels right: more sieving = more sure.
Fix: unnecessary. Stop at p ≤ N p \le \sqrt N p ≤ N
Recall Try before revealing
Why is the trial-division bound n \sqrt n n
Why does the sieve start crossing at p 2 p^2 p 2
Give a composite that fools "check only 2,3,5".
Answers: smaller factor of a pair ≤ n \le\sqrt n ≤ n < p 2 <p^2 < p 2 49 = 7 2 49=7^2 49 = 7 2 77 = 7 ⋅ 11 77=7\cdot11 77 = 7 ⋅ 11
Recall Feynman: explain to a 12-year-oldImagine numbers standing in a line. A prime is a kid who can only make a straight single line of blocks — never a neat rectangle. The Sieve is a game: 2 tells all its "friends" (4, 6, 8…) to sit down. Then 3 does the same, then 5. Whoever is still standing at the end could never sit — they're the primes! And you only need the first few callers, because tall rectangles were already knocked down by short ones.
Mnemonic Remember the method"Square-Root Sieve, Start at the Square."
Test divisors only up to the square root .
In the sieve, start crossing at p 2 p^2 p 2 .
Both tricks come from the same fact: the little factor hides below n \sqrt n n
Prime = exactly two divisors. 1 is neither.
Primality: check divisors 2 → ⌊ n ⌋ 2\to\lfloor\sqrt n\rfloor 2 → ⌊ n ⌋
Sieve: cross multiples of each p p p p 2 p^2 p 2 p ≤ N p\le\sqrt N p ≤ N
Define a prime number A natural number
p > 1 p>1 p > 1 whose only positive divisors are 1 and
p p p (exactly two distinct divisors).
Is 1 prime, composite, or neither? Neither — it has only one divisor, and allowing it would break unique factorisation.
Why need we only trial-divide up to n \sqrt n n If
n = a b n=ab n = ab with
a ≤ b a\le b a ≤ b , then
a ≤ n a\le\sqrt n a ≤ n ; a divisor above
n \sqrt n n forces a partner below it.
In the Sieve, from which multiple do we start crossing out p p p From
p 2 p^2 p 2 — smaller multiples are already crossed by smaller primes.
In the Sieve up to N N N When
p 2 > N p^2>N p 2 > N (i.e.
p > N p>\sqrt N p > N ); remaining numbers are automatically prime.
Give a composite that survives "test only 2,3,5". 49 = 7 2 49=7^2 49 = 7 2 (or
77 = 7 × 11 77=7\times11 77 = 7 × 11 ,
91 = 7 × 13 91=7\times13 91 = 7 × 13 ).
List all primes below 30. 2,3,5,7,11,13,17,19,23,29.
Time complexity of trial division per number? State the Fundamental Theorem of Arithmetic. Every integer
> 1 >1 > 1 factors into primes uniquely (up to order).
Is 91 prime? No,
91 = 7 × 13 91=7\times13 91 = 7 × 13 .
smaller multiples already gone
d with 1 less than d less than n
Fundamental Theorem of Arithmetic
a less than or equal sqrt n
Intuition Hinglish mein samjhoDekho, prime number woh hota hai jiske sirf do divisors hote hain — 1 aur khud woh number. Jaise 7 ko sirf 1 aur 7 hi divide karte hain, isliye 7 prime hai. Agar kisi number ke beech mein koi aur factor mil jaaye (jaise 91 = 7×13), toh woh composite hai. Aur haan, 1 na prime hai na composite — kyunki uske sirf ek hi divisor hai, aur agar 1 ko prime maan lein toh factorisation unique nahi rehti.
Primality test ka smart trick: kisi number n n n n − 1 n-1 n − 1 n \sqrt n n n = a × b n = a\times b n = a × b a ≤ b a \le b a ≤ b a a a n \sqrt n n n \sqrt n n
Sieve of Eratosthenes ek super-fast tareeka hai saare primes ek saath nikalne ka. 2 se 30 tak list banao. Pehle 2 ke multiples kaato, phir 3 ke, phir 5 ke — bas 30 \sqrt{30} 30 p p p p 2 p^2 p 2
