問題
1 より大きい整数は、因数の順序を除けば、ただ 1 通りに素数の積で表せます(算術の基本定理)。たとえば 360 = 2 × 2 × 2 × 3 × 3 × 5 です。この素数の並びを求めることを素因数分解といいます。
prime_factorization(n) を実装してください。
n は最大 10^12 にもなるので、定番の方法は試し割りです。2 で割れるだけ割り、次に 3 で割れるだけ割り、と続けていきます。試す約数 d は、d × d が n のまだ残っている部分以下である間だけで十分で、最後に 1 より大きい数が残れば、それ自体が素数です。こうすれば、n が大きな素数や、大きな 2 つの素数の積であっても、約 √n ≈ 10^6 ステップで済みます。
入力
n: 素因数分解する数。
出力
n の素因数を昇順に返してください。各素数は n を割り切る回数だけ繰り返し、リストの要素をすべて掛けると n になるようにします。n = 1 のときは空のリストを返してください。n が素数なら、リストの要素は n 1 つだけです。
制約
1 ≤ n ≤ 10^12
例
入力:
n = 360
期待される出力:
expected = [2, 2, 2, 3, 3, 5]
入力:
long long n = 360;
期待される出力:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
入力:
long n = 360;
期待される出力:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};
解説
360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5 なので、答えは [2, 2, 2, 3, 3, 5] です。
入力:
n = 97
期待される出力:
expected = [97]
入力:
long long n = 97;
期待される出力:
std::vector<long long> expected = {97};
入力:
long n = 97;
期待される出力:
long[] expected = new long[] {97};
解説
√97 ≈ 9.8 以下の素数(2, 3, 5, 7)はどれも 97 を割り切らないので、97 は素数で、答えは [97] です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
2 で割れるだけ割ったら、3, 5, 7, … と進めていきましょう。
ヒント 2
因数が見つかるたびに n を小さくし、d × d を小さくなった n と比べます。
ヒント 3
ループのあとに 1 より大きい数が残っていれば、それがいちばん大きな素因数です。
目安の計算量
時間 O(√n)、追加メモリ O(log n)(結果のリスト)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。