素因数分解 ヘルプ
目次
素因数分解
素因数分解とは，整数を素数の積で表す方法です．24 を素因数分解すると，24 = 23 × 3 となります．
素因数分解の用途
整数の性質を調べたり，大きな整数の計算を効率的に行ったりするために用いられます．公開鍵暗号方式である RSA 暗号の安全性は素因数分解の困難さに依存しています．
素因数分解のアルゴリズム
対象となる整数を，小さい順に 2 から素数で割り続けて，割り切れる素数を見つけていく方法があります．素因数は必ず対象となる整数の平方根以下となるため，計算を終えてよいかを判定できます．本機能は，このアルゴリズムに少し改良を加えて実装しました．
素因数分解と因数分解の違い
素因数分解は整数を素数の積で表すことです．因数分解は多項式を積の形に分解することです．つまり，対象が整数か多項式かという違いがあります．
最小公倍数の求め方
2 つ以上の整数の最小公倍数を求めるには，それらの数の素因数分解を行い，出現する素因数の最大の指数を用いて計算できます．例えば，12 = 22 × 3, 18 = 2 × 32 であるため，最小公倍数は，22 × 32 = 36 となります．
最大公約数の求め方
2 つ以上の整数の最大公約数を求めるには， それらの数の素因数分解を行い， 共通する素因数の積を求めればよいです．例えば，12 = 22 × 3, 18 = 2 × 32 であるため，最大公約数は， 2 × 3 = 6 となります．