Python程式：按排序順序查詢給定數字的所有質因數

假設我們有一個大於1的數字n，我們必須找到它的所有質因數，並按排序順序返回它們。我們可以將一個數字寫成質數的乘積，它們是它的質因數。同一個質因數可能出現不止一次。

因此，如果輸入是42，則輸出將是[2, 3, 7]。

為了解決這個問題，我們將遵循以下步驟：

• res := 一個新的列表
• 當 n mod 2 等於 0 時，執行以下操作：
  • 將 2 插入到 res 的末尾
  • n := n/2 的商
• 對於範圍從 3 到 (n 的平方根) 的 i，步長為 2：
  • 當 n mod i 等於 0 時，執行以下操作：
    • 將 i 插入到 res 的末尾
    • n := n/i 的商
• 如果 n > 2，則：
  • 將 n 插入到 res 的末尾
• 返回 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]

Arnab Chakraborty

更新於：2020年10月7日

630 次檢視

開啟你的職業生涯

完成課程獲得認證

開始學習