Python勉強③ 素因数分解 2022/06/15

「アルゴリズム×数学」が基礎からしっかり身につく本　で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で割る素因数分解を行った後、奇数でわり、最後に素数でわる、というイメージでしょうか。

二つ目の方が確かに無駄がないですね。