中級 0件解決済み 正答率0%

素因数分解

数を素因数に分解し、小さい順に、重複も含めて並べます。

このチャレンジで学べること

  • 各因数を、含まれている回数だけ割り出す
  • d × d が残りの数を超えたら試し割りをやめる
  • 最後に 1 より大きい数が残れば、それが素因数だと気づく

問題

原文(英語)を表示

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

例

例 1
入力:
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] です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。