Number Theory
Primes, GCD & sequences — the math behind algorithms
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.
Try it interactively
Sieve of Eratosthenes Visualizer
Animated Sieve of Eratosthenes on a number grid — marks primes and crosses out composites, with step controls. Runs in your browser.
Open toolEuclidean Algorithm (GCD) Visualizer
Animated Euclidean algorithm — compute the GCD of two numbers step by step with the (a, b) → (b, a mod b) reduction. Runs in your browser.
Open toolPrime Factorization Visualizer
Animated prime factorization as a factor tree — splits a number into prime factors step by step. Runs in your browser.
Open toolCollatz Conjecture Visualizer
Animated Collatz (3n+1) sequence as a line chart — watch the trajectory climb and fall to 1. Step controls. Runs in your browser.
Open toolPrefer a focused tool?
- Number Theory → See the math behind algorithms, step by step
Frequently asked questions
How does the Sieve of Eratosthenes work?
Starting from 2, it marks every multiple of each prime as composite. Whatever stays unmarked is prime. It finds all primes up to n in about O(n log log n) time — far faster than testing each number individually.
Why is the Euclidean algorithm so fast?
Each step replaces the larger number with the remainder of dividing the two, which shrinks the values at least as fast as the Fibonacci sequence grows. That gives it O(log min(a, b)) running time — only a handful of steps even for huge numbers.