用 Python 编写程序按排序顺序查找给定数字的所有素因数

pythonserver side programmingprogramming更新于 2026/1/12 16:12:17

假设我们有一个大于 1 的数字 n，我们必须找到它的所有素因数并按排序顺序返回它们。我们可以将数字写成素数的乘积，它们是它的素因数。并且相同的素因数可能会出现多次。

因此，如果输入为 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
返回 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))