「アルゴリズム×数学」が基礎からしっかり身につく本 でAtcoderデビューしたいNorthです。
今日は素因数分解について勉強しました。
①平方根までの約数を使う
②素数を使う
2種類の方法を学び、②の方が難しいですが計算速度は早くなることを学びました。
まず①平方根までの約数を使い素因数分解を書き出す方法です。
def Factorization(N):
list = []
for i in range(2, int(N ** 0.5)): #平方根までの約数
while N % i == 0: #割り切れるなら
list.append(i) #リストに追加
N = N / i #素因数分解を継続
if N != 1: #そのものが素数のとき
list.append(int(N))
return list
list = Factorization(int(input()))
print(*list)
知らなかったのですがlistに*をつけることで中の要素を展開してくれるんですね。
②素数を使う方法
これはWikipediaの試し割り法のページと他のページも参考にしました。
n = int(input())
def Factorization(n):
a = []
while n%2 == 0:
a.append(2)
n //= 2
f = 3
while f*f <= n:
if n % f == 0:
a.append(f)
n //= f
else:
f += 2
if n != 1:
a.append(n)
return a
Factorization(n)
2で割る素因数分解を行った後、奇数でわり、最後に素数でわる、というイメージでしょうか。
二つ目の方が確かに無駄がないですね。