素因数分解

素因数分解とは

nを素因酢分解するアルゴリズムは、1 ~ √nに対してaとするとnをaで割れるときにaで割れるだけ割れば良い。この時aが素数でなければaを分解せねばならないが、aは必ず素数である。 最後に残った数は素因数となっているので追加する。ここで1になる可能性があることにも注意せねばならぬ。

実装

必要になったら書きます

応用

約数の個数

素因数分解をn = p1^e1p2^e2...pr^erとする。この時、約数の個数は

(e1 + 1)(e2 + 1)(e3 + 1)...(er + 1)となる。

約数の総和

素因数分解をn = p1^e1p2^e2...pr^erとする。この時、約数の総和は

(p1⁰ + p1¹ + ... + p1^e1)(p2⁰ + p2¹ + ... + p2^e2)...(pr⁰ + pr¹ + ... + pr^er)となる。

オイラー関数

ある整数nが与えられる。この整数に対して互いに素なn未満の整数の個数を φ(n)とかく。これをオイラー関数という。 素因数分解をn = p1^e1p2^e2...pr^erとする。

φ(n) = n (1 - 1/p1)(1 - 1/p2)...(1 - 1/pr)となる。