素因数分解計算機

素因数分解 (素数分解) は、正の整数を素数の積として表現します。1 より大きいすべての整数には一意の素因数分解があります (算術の基本定理)。例: 360 = 2³ × 3² × 5。手順: 最小の素因数を見つけ、除算し、商が 1 になるまで繰り返します。アルゴリズム: √n までの素数で試行除算します。約 10^12 までの数に対して効率的です。より大きな数にはより高度なアルゴリズム (Pollard's rho、number field sieve) が必要です。素因数分解は非常に大きな数に対して計算量的に困難です。この困難さは RSA 暗号化の基礎です。

暗号化: RSA および他の公開鍵システムは、大きな数を因数分解する困難さに依存しています。GCD/LCM の計算: GCD(a,b) = 最小指数の共通素因数の積。LCM(a,b) = 最大指数のすべての素因数の積。分数の簡約: 分子と分母を GCD で除算します。Euler のトーシェント関数: φ(n) = n × ∏(1 - 1/p) 各素因数 p に対して。完全平方の判定: n が完全平方である場合、すべての素因数指数が偶数です。約数の数: (e₁+1)(e₂+1)...(eₖ+1) ここで eᵢ は指数です。

Eratosthenes のふるいは、N までのすべての素数を効率的に見つけます。アルゴリズム: ブール配列 [2..N] を作成し、すべてを true にマークします。2 から始まるマークされていない各数 p に対して: p のすべての倍数 (p²、p²+p、...) を合成数としてマークします。残りのマークされていない数は素数です。時間: O(n log log n)、スペース: O(n)。最適化: p² でマーク付けを開始します (より小さい倍数は既にマークされています)。2 の後の奇数のみをチェックします。N = 10^6 の場合: ~78,498 個の素数。N = 10^9 の場合: メモリを削減するために分割ふるいが必要です。競技プログラミングと数論研究で使用されます。

Euler のトーシェント φ(n) は、1 から n までの整数のうち n と互いに素 (共通因数がない) である整数の数をカウントします。主な性質: φ(1) = 1。素数 p の場合: φ(p) = p − 1。素数の累乗の場合: φ(p^k) = p^k − p^(k-1)。互いに素な a、b に対して: φ(a×b) = φ(a)×φ(b) (乗法的)。一般的: φ(n) = n × ∏(1 − 1/p) n を除算するすべての素数 p に対して。例: φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4。12 と互いに素な整数: {1、5、7、11}。使用: RSA (Euler の定理: a^φ(n) ≡ 1 mod n)、群論。

完全数は、その真の約数 (それ自身を除く約数) の合計に等しい数です。例: 6 = 1+2+3。28 = 1+2+4+7+14。496。8128。51 個の完全数のみが知られています。既知の完全数はすべて偶数です。Mersenne 素数: (2^p - 1) が Mersenne 素数である場合、n = 2^(p-1) × (2^p - 1) は完全です。関連する概念: 過剰数: σ(n) > 2n (すべての約数の合計 > 2×数)。不足数: σ(n) < 2n。友愛数: σ(a) = b+a と σ(b) = a+b の対。例: 220 と 284。