Part IX · Number Theory, Combinatorics and Algebra
52. Number Theory and Prime Algorithms
7 lessons•33 topics•Intermediate / Expert
0 of 7 lessons published
52.01Outline
Divisibility basics
- Divisors
- Multiples
- Prime/composite
- Factor pairs
- Integer square root
- Divisor counting
52.02Outline
GCD and LCM
- Euclidean algorithm
- Extended Euclid
- Bézout identity
- Multiple-number GCD/LCM
52.03Outline
Prime generation
- Trial division
- Sieve of Eratosthenes
- Linear sieve
- Segmented sieve
- Smallest prime factor
52.04Outline
Prime factorization
- Repeated division
- SPF factorization
- Exponent form
- Divisor enumeration
- Number of divisors
- Sum of divisors
52.05Outline
Arithmetic functions
- Euler totient phi
- Mobius mu
- Divisor function
- Multiplicative functions
- Dirichlet convolution intro
52.06Outline
Diophantine equations
- Linear equations ax+by=c
- Existence criterion
- General solution
- Counting bounded solutions
52.07Outline
Advanced primes
- Miller-Rabin primality
- Pollard's rho factorization
- Deterministic 64-bit bases overview