Primes, Sieves, and Integer Factorization
Fundamental theorem of arithmetic, the sieve of Eratosthenes and its linear/segmented cousins, multiplicative functions, and how to factor when you cannot sieve.
Leads to: 19.3 needs primes for Fermat/Euler; 19.5 counts divisors; the Euler Lab’s Number Theory path leans on sieves constantly.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- State the fundamental theorem of arithmetic and explain why Euclid’s lemma is what makes uniqueness true.
- Derive the sieve of Eratosthenes, prove the \(O(n\log\log n)\) bound, and implement it with the \(p^2\) start and odd-only optimizations.
- Implement a smallest-prime-factor sieve and use it to factor \(O(\log n)\)-fast per query.
- Compute multiplicative functions (\(\tau,\ \sigma,\ \varphi,\ \mu\)) from a factorization and via a sieve.
- Choose between trial division, Pollard rho, and a sieve given \(n\) and the number of queries.
Key Vocabulary
- Prime
- An integer \(p\gt 1\) whose only positive divisors are 1 and \(p\). 1 is not prime - that convention is what makes factorization unique.
- Euclid’s lemma
- If \(p\) is prime and \(p\mid ab\) then \(p\mid a\) or \(p\mid b\). This, not existence, is the hard half of unique factorization.
- Sieve of Eratosthenes
- Cross out multiples of each prime \(p\) starting at \(p^2\); survivors are prime. Cost \(O(n\log\log n)\).
- Smallest prime factor (SPF) sieve
- An array where spf[k] is \(k\)’s least prime factor; dividing repeatedly factors any \(k\le n\) in \(O(\log k)\).
- Multiplicative function
- \(f\) with \(f(mn)=f(m)f(n)\) whenever \(\gcd(m,n)=1\). Examples: \(\tau\) (divisor count), \(\sigma\) (divisor sum), \(\varphi\) (totient), \(\mu\) (Möbius).
- Segmented sieve
- Sieve an interval \([L,R]\) using primes up to \(\sqrt R\), so memory is \(O(R-L)\) rather than \(O(R)\).
Intuition & Motivation
Unique factorization
The sieve of Eratosthenes
Mark an array of \(n+1\) booleans as prime. For \(p=2,3,\dots,\lfloor\sqrt n\rfloor\), if \(p\) is still marked, cross out \(p^2,\ p^2+p,\ p^2+2p,\dots\) Start at \(p^2\) because every smaller multiple \(kp,\ k\lt p\) already has a smaller prime factor and was crossed out earlier.
using Mertens’ second theorem (\(M\approx0.2615\) is the Meissel–Mertens constant). For \(n=10^7\) that inner sum is only about 3.0 - the sieve does roughly three passes’ worth of writes over the array. Compare trial division on every number: \(\Theta(n\sqrt n)\), which for \(n=10^7\) is a thousand times worse.
Linear (Euler) sieve and the SPF trick
A refinement crosses out each composite exactly once, by its smallest prime factor. Iterate \(i=2..n\); if spf[i] is unset, \(i\) is prime; then for each prime \(p\le \mathrm{spf}[i]\) with \(ip\le n\), set spf[i*p]=p and break when \(p=\mathrm{spf}[i]\). Cost \(O(n)\), and you keep a factorization oracle: repeatedly divide by spf[k] to factor any \(k\le n\) in \(O(\log k)\) time.
| Task | Best tool | Cost |
|---|---|---|
| All primes \(\le 10^7\) | Eratosthenes (odd-only, bytearray) | \(O(n\log\log n)\) |
| Factor \(10^6\) numbers, all \(\le 10^7\) | SPF sieve, then divide down | \(O(n + q\log n)\) |
| Factor one 60-bit number | Pollard rho + Miller–Rabin | \(O(n^{1/4})\) expected |
| Primes in \([10^{12},10^{12}+10^6]\) | Segmented sieve with base primes to \(10^6\) | \(O((R-L)\log\log R)\) |
| Is this 200-digit number prime? | Miller–Rabin (probabilistic) | \(O(k\log^3 n)\) |
Multiplicative functions from the factorization
If \(n=\prod p_i^{a_i}\) then the divisor count, divisor sum and Euler totient are read straight off the exponents:
Coding workbench
The Euler Lab’s Number Theory path will hand you problems whose stated difficulty is entirely about which sieve you reach for: a naive primality test times out, a plain sieve fits, and a segmented or SPF sieve turns an impossible memory footprint into a comfortable one.
- Starting the crossing-out at \(2p\) instead of \(p^2\) - correct but wasteful; and looping \(p\) past \(\sqrt n\) is pure waste.
- Building a \(10^9\)-entry Python list of booleans (gigabytes). Use bytearray, odd-only indexing, or segment the range.
- Trial-dividing by all integers instead of by primes up to \(\sqrt n\) - and forgetting the leftover: after dividing out all primes \(\le\sqrt n\), any remaining \(k\gt 1\) is itself prime.
- Using \(\varphi(n)=n\prod(1-1/p)\) in floating point. Do it in integers as \(\prod (p-1)p^{e-1}\) or the rounding will bite.
- Assuming a probabilistic primality test is a proof. Miller–Rabin with fixed bases is deterministic below \(3.3\times10^{24}\); above that it is evidence, not proof.
- Sieve once, query many. If a problem asks about every \(n\le N\), almost always the answer is ‘precompute a table in \(O(N\log\log N)\)’ rather than ‘answer each query cleverly’.
- You can sieve any multiplicative function the same way you sieve primes: add \(p\)’s contribution to every multiple of \(p\). Divisor sums, totients and Möbius all fall out in \(O(n\log n)\) or better.
- For one huge number, Pollard’s rho with Brent’s cycle detection finds a factor in \(O(n^{1/4})\) expected time - combine with Miller–Rabin to know when to stop.
Practice this in the Euler Lab
Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.
Warm-up:
#1 Multiples of 3 or 5 (1%, tier A) #2 Even Fibonacci Numbers (1%, tier A) #7 10 001st Prime (1%, tier A) #20 Factorial Digit Sum (1%, tier A)
Applied:
#293 Pseudo-Fortunate Numbers (16%, tier B) #313 Sliding Game (16%, tier B) #357 Prime Generating Integers (16%, tier B)
Challenge:
#161 Triominoes (41%, tier C) #182 RSA Encryption (41%, tier C)
481 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.
Knowledge Check
Practical Exercise
(a) Prove that if \(n\) is composite it has a prime factor \(\le\sqrt n\), and explain why this bounds trial division. (b) Design a segmented sieve that lists the primes in \([L,R]\) with \(R\le10^{12}\) and \(R-L\le10^6\), and state its time and memory cost. (c) Show \(\sum_{d\mid n}\varphi(d)=n\).
(a) Write \(n=ab\) with \(1\lt a\le b\lt n\). If both \(a,b\gt \sqrt n\) then \(ab\gt n\), contradiction; so \(a\le\sqrt n\), and any prime factor of \(a\) is a prime factor of \(n\) that is \(\le\sqrt n\). Hence testing divisibility by primes up to \(\lfloor\sqrt n\rfloor\) suffices: cost \(O(\sqrt n/\log n)\) divisions.
(b) First sieve all primes \(p\le\sqrt R\le10^6\) (cheap, \(O(\sqrt R\log\log R)\)). Allocate a bytearray of length \(R-L+1\) indexed by \(x-L\). For each base prime \(p\), find the first multiple \(\ge L\), namely \(m=\max(p^2,\ \lceil L/p\rceil p)\), and cross out \(m, m+p,\dots\le R\). Survivors \(\gt 1\) are prime. Time \(O(\sqrt R\log\log R + (R-L)\log\log R)\); memory \(O(\sqrt R + (R-L))\) bytes - about 2 MB here, versus 1 TB for a full sieve to \(10^{12}\).
(c) Partition \(\{1,\dots,n\}\) by \(g=\gcd(k,n)\). For each divisor \(d\mid n\), the \(k\) with \(\gcd(k,n)=d\) are exactly \(k=d j\) with \(1\le j\le n/d\) and \(\gcd(j,n/d)=1\), of which there are \(\varphi(n/d)\). Summing the sizes of the blocks: \(n=\sum_{d\mid n}\varphi(n/d)=\sum_{d\mid n}\varphi(d)\), since \(d\mapsto n/d\) permutes the divisors.
Lesson Summary
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: Work is \(\sum_{p\le n} n/p\), and the sum of reciprocals of primes grows like \(\ln\ln n\) (Mertens), not \(\ln n\). Only primes announce their multiples, and primes thin out.
A: \(\tau=\prod(a_i+1)\); \(\sigma=\prod\frac{p_i^{a_i+1}-1}{p_i-1}\); \(\varphi=\prod (p_i-1)p_i^{a_i-1}\) (compute in integers, never floats).
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Source References
This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.
- Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Ch. I.4 - Strong induction and the well-ordering principle, used here for existence of factorizations and for bounding the sieve’s work.
- The Pragmatic Programmer (Thomas & Hunt, 2nd/20th Anniv. ed., 2019) current - Ch. 7 (While You Are Coding) - Choosing the right data structure (bytearray vs list) and precomputing tables: engineering decisions that turn an \(O(n\sqrt n)\) idea into an \(O(n\log\log n)\) program.
- Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lecture 32 (operation counts) - Cost models and the discipline of counting operations before you run anything - the same accounting used for (19.3).