Core · Module 12 · Lesson 2 of 4
Prime Sieves (Eratosthenes & Linear Sieve) and Prime Factorization
Test primality and factorize single integers in O(sqrt(n)), generate all primes up to n in O(n log log n) with the Sieve of Eratosthenes, and factorize 10^6 queries in O(log n) each using Smallest Prime Factors (SPF).
By the end you can
- Prove why every composite number n has a prime factor <= sqrt(n) and factorize a single integer in O(sqrt(n))
- Implement the Sieve of Eratosthenes starting inner loops at i * i in O(n log log n) time
- Precompute a Smallest Prime Factor (SPF) array to factorize any query x <= n in O(log x) divisions
Builds on Euclidean GCD, Modular Arithmetic, and Binary Exponentiation.
01 · A question first
If a problem asks you to factorize 500,000 numbers up to 1,000,000, running an O(sqrt(n)) loop per query takes 500 million operations and times out. How can a 4 MB table precomputed in 10 milliseconds factorize each query in at most 20 steps?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Intuitive Explanation & Real-World Analogy
- Core Concepts & Visual Walkthrough
- Pseudocode
- Multi-Language Implementations (C++, Java, Python)
- Time & Auxiliary Space Complexity Derivation
- Edge Cases & Common Beginner Mistakes
- Alternative Approaches (Brute Force vs. Optimal)
- Pattern Recognition Guide & Three-Stage Practice Plan
03 · Practice
Something wrong with this lesson? Report a problem