素因数分解計算機

素因数分解計算機 - 数を分解

🔢 任意の数を素因数に分解できます。積の形、指数付き表示、 因数分解ツリー、ステップごとの割り算手順を確認できます。

素因数分解とは？

素因数分解（整数の因数分解）とは、合成数を素数の積として表す手続きです。 すべての合成数は一意の素因数分解を持ちます。

算術の基本定理

1より大きい任意の整数は、素数の積として（因数の順序を除いて）一意に表されます。 これは数論における最も重要な定理の一つです。

表示形式

積の形: 2 × 2 × 3 × 5

指数の形: 2² × 3 × 5

指数表記: 2² · 3¹ · 5¹

例

例1: 12

• 12 = 2 × 2 × 3
• 12 = 2² × 3
• 素因数: 2, 3

例2: 60

• 60 = 2 × 2 × 3 × 5
• 60 = 2² × 3 × 5
• 素因数: 2, 3, 5

例3: 100

• 100 = 2 × 2 × 5 × 5
• 100 = 2² × 5²
• 素因数: 2, 5

分解の方法

1. 試し割り:

• 小さな素数（2, 3, 5, 7...）から順に割ります
• 商が1になるまで続けます
• 簡単ですが、大きい数では遅くなる場合があります

2. 因数分解ツリー:

• 数を任意の2つの因数に分けます
• すべての因数が素数になるまで続けます
• 視覚的で理解しやすい方法です

3. 素数で割る方法:

• 素数のみで割ります
• すべての数を試すより効率的です
• コンピュータで一般的なアルゴリズムです

手順: 60の分解

60 ÷ 2 = 30   (2は素数)
30 ÷ 2 = 15   (2は素数)
15 ÷ 3 = 5    (3は素数)
5 ÷ 5 = 1     (5は素数)

結果: 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5
            

すべての約数を求める

素因数分解が分かれば、すべての約数を求められます：

例: 60 = 2² × 3¹ × 5¹

• 各素因数について、指数を0から最大まで選びます
• 2⁰ または 2¹ または 2² → (1, 2, 4)
• 3⁰ または 3¹ → (1, 3)
• 5⁰ または 5¹ → (1, 5)
• 組み合わせをすべて掛け合わせます
• 約数: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

約数の個数の公式

n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ のとき

約数の個数 = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)

例: 60 = 2² × 3¹ × 5¹

• 約数の個数 = (2+1) × (1+1) × (1+1)
• = 3 × 2 × 2 = 12個

約数の和の公式

和 = [(p₁^(a₁+1) - 1)/(p₁ - 1)] × [(p₂^(a₂+1) - 1)/(p₂ - 1)] × ...

例: 60 = 2² × 3 × 5

• 和 = [(2³-1)/(2-1)] × [(3²-1)/(3-1)] × [(5²-1)/(5-1)]
• = [7/1] × [8/2] × [24/4]
• = 7 × 4 × 6 = 168

素因数分解の応用

• 暗号: RSA暗号は大きな数の分解の難しさに依存します
• 最大公約数/最小公倍数: GCD・LCMの計算
• 分数の約分: 最簡分数への簡約
• 数論: 整数の性質の研究
• 計算機科学: ハッシュ関数、アルゴリズム

特別な数の種類

完全数:

• 真の約数の和が自分自身に等しい
• 6 = 1 + 2 + 3
• 28 = 1 + 2 + 4 + 7 + 14

過剰数:

• 真の約数の和が自分自身より大きい
• 12: 約数の和 = 1+2+3+4+6 = 16 > 12

不足数:

• 真の約数の和が自分自身より小さい
• 8: 約数の和 = 1+2+4 = 7 < 8

2の冪

2の冪は分解が非常にシンプルです：

• 16 = 2⁴
• 64 = 2⁶
• 256 = 2⁸
• 1024 = 2¹⁰

高合成数

自分より小さいすべての正の整数よりも約数の個数が多い数：

• 1（約数1個）
• 2（約数2個）
• 4（約数3個）
• 6（約数4個）
• 12（約数6個）
• 24（約数8個）
• 36（約数9個）
• 60（約数12個）

分解の難しさ

• 小さな数: 手計算で簡単に分解可能
• 大きな素数: 分解は非常に困難
• 半素数: 2つの素数の積で、RSAの基礎
• 200桁以上: 古典計算機では現実的に困難
• 量子計算: ショアのアルゴリズムは効率的に分解可能

よくある分解

• 10 = 2 × 5
• 12 = 2² × 3
• 15 = 3 × 5
• 24 = 2³ × 3
• 30 = 2 × 3 × 5
• 36 = 2² × 3²
• 48 = 2⁴ × 3
• 100 = 2² × 5²
• 144 = 2⁴ × 3²
• 360 = 2³ × 3² × 5

💡 プロのコツ: 小さな素数で割り切れるか素早く判断するには、 末尾が偶数なら2で割れる、各桁の和が3で割れるなら3で割れる、末尾が0または5なら5で割れる、 各桁の和が9で割れるなら9で割れる、交互和が11で割れるなら11で割れる…などを覚えておきましょう。 例：4356 は 4+3+5+6 = 18（9で割れる）なので 4356 は9で割れます！ 大きな素数を試す前に、まずはこれらのチェックから始めてください。