Phân Tích Thừa Số Nguyên Tố Seri Linh Kiện

Mô tả

Tại nhà máy Samsung Bắc Ninh, mỗi lô linh kiện điện tử đều được in một số seri duy nhất dưới dạng một số nguyên dương. Kỹ sư kiểm định chất lượng muốn mã hóa số seri này thành một dãy thừa số nguyên tố, phục vụ việc truy xuất nguồn gốc khi có lỗi hàng loạt.

Nhiệm vụ của bạn là viết một chương trình nhận vào số seri n và phân tích n thành tích các thừa số nguyên tố. Nếu một thừa số nguyên tố p xuất hiện k lần trong tích (tức là p^k chia hết cho n nhưng p^(k+1) không), thì p phải xuất hiện đúng k lần trong dãy kết quả. Các thừa số trong kết quả được sắp xếp theo thứ tự tăng dần.

Đầu vào

• Một số nguyên dương n (2 ≤ n ≤ 10^9).

Đầu ra

• Một danh sách các số nguyên tố, là kết quả phân tích n thành thừa số nguyên tố, sắp xếp theo thứ tự tăng dần.

Ràng buộc

• 2 ≤ n ≤ 10^9.
• Kết quả luôn có ít nhất một phần tử vì n ≥ 2.

Ví dụ

Ví dụ 1:

• Đầu vào: n = 84
• Đầu ra: [2, 2, 3, 7]
• Giải thích: Ta phân tích 84 từng bước. 84 chia hết cho 2, được 42. 42 chia hết cho 2, được 21. 21 chia hết cho 3, được 7. 7 là số nguyên tố. Vậy 84 = 2 × 2 × 3 × 7, kết quả là [2, 2, 3, 7].

Ví dụ 2:

• Đầu vào: n = 97
• Đầu ra: [97]
• Giải thích: 97 là số nguyên tố, không thể phân tích thêm, nên kết quả chỉ chứa chính nó.