NTL1A 素因数分解

はじめに

カテゴリー競プロ初中級者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を取り出し、niで割り切れるだけ割り続けてnを更新する
    • 割るたびに解答リストに追加する

ポイント

  • 探索リストは2~Nではなく2~sqrt(N)としても良い。
    • ただし、終了状態でn=1となっていない場合があるので、最後にnを解答リストに追加する。このnは素数であることが保証されている。

解説

niで割り切れた場合に解答リストに追加を行うが、その場合はiが素数であることは保証されている。その理由は考察する。

仮にiが合成数であった場合、iiより小さい素数のいくつかの積で表すことができる。しかし、アルゴリズムの最中でnに対して割り切れるだけ割っているため、必ずiで割り切ることはできなくなっているはずである。ゆえにiは素数である。

同様の理由でポイントで述べた終了状態のnが素数であることを説明できる。

コード

1
2
3
4
5
6
7
8
9
10
11
12
N = int(input())
n = N
ans = []
for i in range(2,int(N**0.5)+1): # intに変換すること
while(n%i==0):
n //= i # 整数除算(//)を使うこと
ans.append(i)
if n!=1:
ans.append(n)
ans = [str(a) for a in ans]
ans = str(N)+": " + " ".join(ans)
print (ans)

記事情報

  • 投稿日:2020年4月30日
  • 最終更新日:2020年5月10日