競プロ初中級者100問

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を取り出し、nがiで割り切れるだけ割り続けてnを更新する
    • 割るたびに解答リストに追加する

ポイント

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

解説

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

仮にiが合成数であった場合、iはiより小さい素数のいくつかの積で表すことができる。しかし、アルゴリズムの最中で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日