Chương trình tìm tất cả các thừa số nguyên tố của một số nhất định theo thứ tự được sắp xếp trong Python

Giả sử chúng ta có một số n lớn hơn 1, chúng ta phải tìm tất cả các thừa số nguyên tố của nó và các thừa số nguyên tố trong dãy đã sắp xếp. Chúng ta có thể viết ra một số dưới dạng tích của các số nguyên tố, chúng là thừa số nguyên tố. Và cùng một hệ số nguyên tố có thể xuất hiện nhiều lần.

Vì vậy, nếu đầu vào là 42, thì đầu ra sẽ là [2, 3, 7].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• res:=một danh sách mới
• trong khi n mod 2 giống 0, hãy thực hiện
  • chèn 2 vào cuối res
  • n:=thương số của n / 2
• đối với tôi trong phạm vi 3 đến (căn bậc hai của n), tăng ở bước 2
  • trong khi n mod, tôi giống với 0, hãy thực hiện
    • chèn tôi vào cuối res
    • n:=thương số của n / i
• nếu n> 2, thì
  • chèn n vào cuối res
• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

42

Đầu ra

[2, 3, 7]