Tìm thừa số nguyên tố lớn nhất của một số bằng C ++.

Xét ta có một phần tử x, ta phải tìm thừa số nguyên tố lớn nhất của x. Nếu giá trị của x là 6 thì thừa số nguyên tố lớn nhất là 3. Để giải quyết vấn đề này, chúng ta sẽ phân tích một số bằng cách chia nó với ước của một 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);
}

Đầu ra

Max Prime factor of 162378 is 97