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
Prefer a focused tool?
- Number Theory → See the math behind algorithms, step by step
常见问题
什么是考拉兹猜想？
从任意一个正整数出发：如果是偶数，就除以2；如果是奇数，就计算3n+1。该猜想认为，无论起始数字是多少，这个过程最终都会归于1。
考拉兹猜想已经被证明了吗？
还没有。尽管经过了大量的研究尝试，这个猜想至今仍未被证明，不过计算机验证已经确认，在极大范围内的所有起始数字都符合这一规律。
为什么数字27特别有意思？
从27开始，这个数列要经过111步，并且一度攀升到9232这么高，才最终降到1——对于这样一个不起眼的起始数字来说，这段历程出乎意料地跌宕起伏。
这个数列叫什么名字？
这一系列数值被称为考拉兹轨迹（或3n+1轨迹），而归于1所需的步数则被称为该轨迹的总停止时间（total stopping time）。