Pythonでソートされた順序で指定された数のすべての素因数を見つけるプログラム

数nが1より大きいとすると、その素因数をすべて見つけて、ソートされた順序で返す必要があります。素数の積として数を書き出すことができます、それらは素因数です。また、同じ素因数が複数回発生する可能性があります。

したがって、入力が42のような場合、出力は[2、3、7]になります。

これを解決するには、次の手順に従います-

• res：=新しいリスト
• n mod 2は0と同じですが、
  • resの最後に2を挿入
  • n：=n/2の商
• 範囲3から（nの平方根）のiの場合、ステップ2で増加します
  • n mod iは0と同じですが、
    • resの最後にiを挿入
    • n：=n/iの商
• n> 2の場合、
  • resの最後にnを挿入
• return 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]