Chương trình tìm tất cả thừa số nguyên tố của một số theo thứ tự tăng dần trong Python

Cho số nguyên n > 1, tìm tất cả thừa số nguyên tố của nó và trả về theo thứ tự tăng dần. Thừa số nguyên tố có thể lặp lại.

Ví dụ

Đầu vào: 42.
Đầu ra: [2, 3, 7].

Thuật toán

1. Khởi tạo danh sách kết quả res rỗng.
2. Chia liên tục cho 2 cho đến khi không chia hết, mỗi lần thêm 2 vào res.
3. Duyệt i từ 3 đến sqrt(n), bước nhảy 2:
   • Chia liên tục cho i cho đến khi không chia hết, mỗi lần thêm i vào res.
4. Nếu sau vòng lặp n > 2, thêm n vào res (n là số nguyên tố lớn).
5. Trả về res.

Mã nguồn Python

class Solution:
    def solve(self, n):
        res = []
        while n % 2 == 0:
            res.append(2)
            n //= 2
        for i in range(3, int(n**0.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 / Đầu ra

Input: 42
Output: [2, 3, 7]