Trong bài toán này, chúng ta được cho một số nguyên N <= 10^18. Nhiệm vụ là in ra tất cả các thừa số nguyên tố của số đó kèm theo tần suất xuất hiện của chúng.
Hãy xem ví dụ sau để hiểu rõ vấn đề:
Input: 100 Output: 2 2 5 2 Giải thích: phân tích thừa số nguyên tố của 100 = 2 * 2 * 5 * 5.
Để giải quyết bài toán, chúng ta phải tìm các thừa số nguyên tố của số và tính tần suất của chúng.
Cách làm: tìm tần suất của thừa số 2 và chia số cho 2. Sau đó kiểm tra từ 3 đến căn bậc hai của n. Chia và tăng tần suất của mỗi số nguyên tố là ước của số. Dừng lại khi số trở thành 1. Sau đó in ra tất cả các số nguyên tố kèm tần suất.
Đoạn mã dưới đây minh họa cách triển khai giải pháp:
Ví dụ
#include <iostream> #include <math.h> using namespace std; void factorize(long long n){ int count = 0; while (!(n % 2)) { n/= 2; count++; } if (count) cout<<2<<"\t"<<count<<endl; for (long long i = 3; i <= sqrt(n); i += 2) { count = 0; while (n % i == 0) { count++; n = n / i; } if (count) cout<<i<<"\t"<<count<<endl; } if (n > 2) cout<<n<<"\t"<<1<<endl; } int main() { long long N = 21000; cout<<"Các thừa số nguyên tố và tần suất của số "<<N<<" là \n"; factorize(N); return 0; }Kết quả
Các thừa số nguyên tố và tần suất của số 21000 là 2 3 3 1 5 3 7 1