Link Sub: http://www.spoj.com/PTIT/problems/BCFACTOR/
Người Gửi: Dương Lee
- Problem:
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ố.Input
Một dòng duy nhất chứa số n.
Output
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.
Example:
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.
Input
4
Output:
2 2
Input
168
Output:
2 3
3 1
7 1
- Solution:
Code C:Input
168
Output:
2 3
3 1
7 1
- Tìm tất cả các ước của N trong khoảng [2,sqrt(N)];
- Với mỗi ước: kiểm tra xem có phải số nguyên tố hay không?
- Với mỗi ước nguyên tố: đếm xem N chia tối đa được bao nhiêu ước nt đó. (Sau mỗi lần chia thì N sẽ thay đổi)