Thừa số nguyên tố là một số nguyên tố là ước của số cho trước.
Ước của một số là các số nhân với nhau cho ra số đó.
Phân tích thừa số nguyên tố là quá trình đệ quy chia số cho các thừa số nguyên tố của nó để tìm tất cả các thừa số nguyên tố của số đó.
Ví dụ: N = 120 Thừa số nguyên tố = 2 5 3 Phân tích: 2 * 2 * 2 * 3 * 5
Một số lưu ý về thừa số nguyên tố của một số:
- Tập hợp các thừa số nguyên tố của một số là duy nhất.
- Phân tích thừa số quan trọng trong nhiều phép tính toán học như kiểm tra tính chia hết, tìm mẫu số chung, v.v.
- Đây là khái niệm quan trọng trong mật mã học.
Chương trình tìm thừa số nguyên tố của một số
Ví dụ
#include <iostream> #include <math.h> using namespace std; void printPrimeFactors(int n) { while (n%2 == 0){ cout<<"2\t"; n = n/2; } for (int i = 3; i <= sqrt(n); i = i+2){ while (n%i == 0){ cout<<i<<"\t"; n = n/i; } } if (n > 2) cout<<n<<"\t"; } int main() { int n = 2632; cout<<"Thừa số nguyên tố của "<<n<<" là :\t"; printPrimeFactors(n); return 0; }Kết quả
Thừa số nguyên tố của 2632 là :2 2 2 7 47