BCFACTOR spoj – Phân tích ra thừa số nguyên tố

Nguồn đề bài http://www.spoj.com/PTIT/problems/BCFACTOR/

1. Đề bài BCFACTOR spoj

Cho số nguyên dương n (2<=n<=10^9) , hãy phân tích n ra thừa số nguyên tố.

Dữ liệu

Một dòng duy nhất chứa số n.

Kết quả

Mỗi dòng ghi một thừa số nguyên tố và số mũ tương ứng cách nhau bởi dấu cách.

Các thừa số nguyên tố in ra theo thứ tự tăng dần.

Ví dụ

INPUTOUTPUT
42 2
INPUTOUTPUT
1682 33 17 1

2. Hướng dẫn BCFACTOR spoj

Theo toán học 1 số chỉ có thể chia hết cho các số từ 1 đến căn bậc 2 của số đó. vì vậy chỉ cần duyệt đếm kết quả nếu chia hết N cho i, với i từ 2-> sqrt(n). ở mỗi bước ta phải cập nhật lại N. thực hiện cho đến khi n=1.

3. code tham khảo BCFACTOR spoj

2 thoughts on “BCFACTOR spoj – Phân tích ra thừa số nguyên tố

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *