Xét chúng ta có một phần tử x, chúng ta phải tìm thừa số nguyên tố lớn nhất của x. Nếu giá trị x là 6, thì thừa số nguyên tố lớn nhất là 3. Để giải quyết bài toán này, chúng ta sẽ chỉ phân tích thừa số nguyên tố của số bằng cách chia nó cho ước số của số và theo dõi thừa số nguyên tố lớn nhất.
Ví dụ
#include <iostream> #include<cmath> using namespace std; long long getMaxPrimefactor(long long n) { long long maxPF = -1; while (n % 2 == 0) { maxPF = 2; n /= 2; } for (int i = 3; i <= sqrt(n); i += 2) { while (n % i == 0) { maxPF = i; n = n / i; } } if (n > 2) maxPF = n; return maxPF; } int main() { long long n = 162378; cout << "Max Prime factor of " << n << " is " << getMaxPrimefactor(n); }
Kết quả
Max Prime factor of 162378 is 97