Number Theory

Number theory underpins cryptography, hashing and countless coding-interview problems. A little of it goes a long way.

Primes & factorization

The Sieve of Eratosthenes finds all primes up to n by repeatedly crossing out multiples, running in about O(n log log n) — far faster than testing each number alone. Prime factorization breaks a number into its prime building blocks, the foundation of RSA-style cryptography and of computing least common multiples.

The Euclidean algorithm

The Euclidean algorithm computes the greatest common divisor of two numbers in logarithmic time using nothing but repeated remainder: gcd(a, b) = gcd(b, a mod b). It is one of the oldest algorithms still in everyday use, from simplifying fractions to modular inverses.

Sequences & conjectures

Famous sequences make great visual playgrounds. The Collatz conjecture — repeatedly halve even numbers and triple-and-add-one odd ones — always seems to reach 1, yet no one has proved it must. Watch the orbit bounce toward 1 below.