はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A&lang=ja
素因数分解の問題です。試し割り法と呼ばれるアルゴリズムで解くことができます。
試し割り法のアルゴリズム
N
のコピーn
を用意する。- 空の解答リストを用意する。
2~N
の探索リストを作成する- 探索リストから数
i
を取り出し、n
がi
で割り切れるだけ割り続けてn
を更新する- 割るたびに解答リストに追加する
ポイント
- 探索リストは
2~N
ではなく2~sqrt(N)
としても良い。- ただし、終了状態で
n=1
となっていない場合があるので、最後にn
を解答リストに追加する。このn
は素数であることが保証されている。
- ただし、終了状態で
解説
n
がi
で割り切れた場合に解答リストに追加を行うが、その場合はi
が素数であることは保証されている。その理由は考察する。
仮にi
が合成数であった場合、i
はi
より小さい素数のいくつかの積で表すことができる。しかし、アルゴリズムの最中でn
に対して割り切れるだけ割っているため、必ずi
で割り切ることはできなくなっているはずである。ゆえにi
は素数である。
同様の理由でポイント
で述べた終了状態のn
が素数であることを説明できる。
コード
1 | N = int(input()) |
記事情報
- 投稿日:2020年4月30日
- 最終更新日:2020年5月10日