Math / Number Theory
Primes, GCD & modular arithmetic
Sieve of Eratosthenes
Finds every prime up to n by crossing out the multiples of each prime, starting from its square.
Time O(n log log n) · Space O(n)
Euclidean Algorithm (GCD)
Computes the greatest common divisor by replacing the pair (a, b) with (b, a mod b) until the remainder is zero.
Time O(log min(a, b)) · Space O(1)
Extended Euclidean Algorithm
Runs Euclid while tracking Bézout coefficients, so it ends with gcd(a, b) = x·a + y·b — the key to modular inverses.
Time O(log min(a, b)) · Space O(1)
Fast Exponentiation
Computes baseᵉˣᵖ mod m in O(log exp) by squaring the base and multiplying it in only where the exponent has a 1-bit.
Time O(log exp) · Space O(1)