요소 x가 있다고 가정하고 x의 가장 큰 소인수를 찾아야 합니다. x의 값이 6이면 가장 큰 소인수는 3입니다. 이 문제를 해결하기 위해 숫자를 숫자의 제수로 나누어 인수분해하고 최대 소인수를 추적합니다.
예시
#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); }
출력
Max Prime factor of 162378 is 97