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]

更新于：2020年10月7日

630 次查看

开启你的职业生涯

完成课程获得认证

开始学习
广告