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
エラトステネスの篩 ビジュアライザー
エラトステネスの篩(ふるい)アルゴリズムを数字グリッド上でアニメーション表示するツール。素数にマークを付け、合成数を消していく様子をステップごとに確認できます。すべてブラウザ内で動作します。
ツールを開くユークリッドの互除法ビジュアライザー(GCD)
ユークリッドの互除法をアニメーションで表示 — (a, b) → (b, a mod b) という置き換えを繰り返しながら、2つの数の最大公約数(GCD)をステップごとに計算します。ブラウザ上でそのまま動作します。
ツールを開く素因数分解ビジュアライザー
因数分解ツリーで素因数分解をアニメーション表示 — 数を1ステップずつ素因数へ分解していきます。ブラウザだけで動作します。
ツールを開くコラッツ予想ビジュアライザー
コラッツ数列(3n+1)を動的な折れ線グラフで表示 — 1に到達するまでの増減の軌跡を追跡できます。ステップごとの操作に対応。ブラウザ上ですぐに実行できます。
ツールを開く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)」と呼ばれます。