Pythonで整数のすべての素因数をソート順に求めるプログラム

1より大きい整数 n が与えられたとき、その数のすべての素因数を見つけ、昇順(ソートされた順序)で返すことを考えます。

任意の整数は素数の積として表すことができ、これらの素数がその数の素因数となります。なお、同じ素因数が複数回現れる場合もあります(例：12 = 2 × 2 × 3)。

例えば、入力が 42 の場合、出力は [2, 3, 7] となります。

解法のアプローチ

この問題は「試し割り法」と呼ばれる手法で解くことができます。手順は以下の通りです。

• 結果を格納する新しいリスト res を用意する
• n が 2 で割り切れる間、以下を繰り返す
  • res の末尾に 2 を追加する
  • n := n ÷ 2 の商とする
• i を 3 から √n まで 2 ずつ増やしながら、以下を繰り返す
  • n が i で割り切れる間、以下を繰り返す
    • res の末尾に i を追加する
    • n := n ÷ i の商とする
• もし n > 2 ならば、
  • res の末尾に n を追加する
• res を返す

それでは、実際の実装を見て理解を深めましょう。

実装例

class Solution:
    def solve(self, n):
        res=[]
        while n%2==0:
            res.append(2)
            n//=2
        for i in range(3,int(n**.5)+1,2):
            while n%i==0:
                res.append(i)
                n//=i
        if n>2:
            res.append(n)
        return res
ob = Solution()
print(ob.solve(42))

入力

42

出力

[2, 3, 7]

アルゴリズムのポイント

このアルゴリズムでは、小さい素数から順に割っていくため、結果は自動的に昇順に並びます。また、約数を調べる範囲を √n までに限定することで、計算量は O(√n) に抑えられます。ループ終了後に n が 2 より大きい場合は、残った n 自身が素因数であることを意味するため、リストに追加しています。