Week 40 of 43
CP Track
WEEK 40 LEARNING MODULE
Numerics & Number Theory
Covers fundamental number theory: Euclidean GCD algorithm ($O(\log n)$), Sieve of Eratosthenes ($O(n \log \log n)$), prime factorization, and modular arithmetic.
6 Practice Problems4 Core ConceptsVerified Curriculum: high Confidence
What You'll Learn
- ✓Master Euclidean Algorithm for Greatest Common Divisor (GCD) in $O(\log(\min(a, b)))$ time.
- ✓Implement Sieve of Eratosthenes to precompute all prime numbers up to $N$ in $O(n \log \log n)$ time.
- ✓Perform prime factorization and compute Least Common Multiples (LCM) via $\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$.
- ✓Apply Modular Arithmetic properties: addition, multiplication, and modular exponentiation ($O(\log b)$).
Core Concepts
Euclidean GCD Algorithm
O(log(min(a, b)))Computing gcd(a, b) = gcd(b, a % b) until remainder is zero in logarithmic steps.
Sieve of Eratosthenes
O(n log log n)Iteratively marking multiples of each prime starting from p² to find all primes <= N.
Prime Factorization
O(sqrt(n))Decomposing numbers into products of prime factors in O(sqrt(n)) time.
Modular Arithmetic Laws
O(1)Distributing modulo over addition and multiplication to prevent integer overflow in large calculations.
Algorithms Covered
Euclidean GCD Algorithm ($O(\log n)$)Sieve of Eratosthenes ($O(n \log \log n)$)Prime Factorization ($O(\sqrt{n})$)Modular Exponentiation ($O(\log b)$)
Data Structures Applied
Boolean Prime Arrays / BitsetsIntegers
“The enchanting charms of this sublime science reveal only to those who have the courage to go deeply into it.”
— Carl Friedrich Gauss