Prime numbers — Sieve of Eratosthenes, primality testing

1.1.8 · Maths › Arithmetic & Number Systems

2. Trial-division primality test — scratch se derive karo (HOW + WHY)

Goal: decide karo ki $n$ prime hai ya nahi.

Naive tarika: $2$ se $n - 1$ tak har $d$ test karo. Agar koi $n$ ko divide na kare, toh prime hai. Sahi hai lekin slow hai.

Key optimisation — $n$ kyun?

Maano $n$ composite hai, toh $n = a \times b$ jahan $1 < a \leq b < n$ .

Toh test yeh ban jaata hai:

$check d = 2, 3, 4, \dots, ⌊ n ⌋$

Cost $O (n)$ se gir ke $O (n)$ ho jaati hai.

3. Sieve of Eratosthenes — first principles se banao

Idea: Numbers ko ek-ek karke test karne ki jagah, har prime ke saare multiples cross out karo. Jo bachta hai woh prime hai.

Figure — Prime numbers — Sieve of Eratosthenes, primality testing

4. Common mistakes (Steel-man → Fix)

5. Active recall

Recall Pehle khud try karo, phir reveal karo

Trial-division bound $n$ kyun hai?
Sieve $p^{2}$ se crossing kyun shuru karta hai?
Ek aisa composite do jo "sirf 2,3,5 check karo" se bachke nikal jaaye.

Answers: pair ka chhota factor $\leq n$ hota hai; multiples $< p^{2}$ pehle hi chhote primes se cross ho gaye hain; $49 = 7^{2}$ ya $77 = 7 \cdot 11$ .

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho numbers ek line mein khade hain. Prime woh baccha hai jo sirf blocks ki seedhi single line bana sakta hai — kabhi ek neat rectangle nahi. Sieve ek game hai: 2 apne saare "doston" (4, 6, 8…) ko baith jaane kehta hai. Phir 3 wahi karta hai, phir 5. Akhir mein jo bhi khada rehta hai woh kabhi baith nahi sakta — woh primes hain! Aur tumhe sirf pehle kuch callers chahiye, kyunki bade rectangles pehle hi chhote waalon ne gira diye hote hain.

6. The 80/20 core

Prime = exactly do divisors. 1 na prime na composite.
Primality: $2 \to ⌊ n ⌋$ tak divisors check karo.
Sieve: har $p$ ke multiples $p^{2}$ se cross karo; $p \leq N$ par ruko; survivors prime hain.

Define a prime number

Ek natural number

p > 1

jiske sirf positive divisors 1 aur

p

hain (exactly do distinct divisors).

Is 1 prime, composite, or neither?

Neither — uska sirf ek divisor hai, aur isko allow karne se unique factorisation toot jaata hai.

Why need we only trial-divide up to

n

Agar

n = ab

jahan

a \leq b

, toh

a \leq n

;

n

se upar ka divisor ek partner

n

se neeche force karta hai.

In the Sieve, from which multiple do we start crossing out

p

p^{2}

se — chhote multiples pehle hi chhote primes se cross ho chuke hain.

In the Sieve up to

N

, when do we stop sieving?

Jab

p^{2} > N

ho (yaani

p > N

); baaki numbers automatically prime hain.

Give a composite that survives "test only 2,3,5".

49 = 7^{2}

(ya

77 = 7 \times 11

91 = 7 \times 13

List all primes below 30.

2,3,5,7,11,13,17,19,23,29.

Time complexity of trial division per number?

O (n)

State the Fundamental Theorem of Arithmetic.

Har integer

> 1

uniquely primes mein factor hota hai (order ko chhodke).

Is 91 prime?

Nahi,

91 = 7 \times 13

Connections

Fundamental Theorem of Arithmetic
Divisibility rules
GCD and LCM
Modular arithmetic
Time complexity Big-O
Factorisation