Find largest prime factor of a number | C ++ Program to find largest prime factor of number ; A function to find largest prime factor ; Initialize the maximum prime factor variable with the lowest one ; Print the number of 2 s that divide n ; n >>= 1 ; equivalent to n /= 2 ; n must be odd at this point ; now we have to iterate only for integers who does not have prime factor 2 and 3 ; This condition is to handle the case when n is a prime number greater than 4 ; Driver program to test above function
#include <iostream> NEW_LINE #include <bits/stdc++.h> NEW_LINE using namespace std ; long long maxPrimeFactors ( long long n ) { long long maxPrime = -1 ; while ( n % 2 == 0 ) { maxPrime = 2 ; } while ( n % 3 == 0 ) { maxPrime = 3 ; n = n / 3 ; } for ( int i = 5 ; i <= sqrt ( n ) ; i += 6 ) { while ( n % i == 0 ) { maxPrime = i ; n = n / i ; } while ( n % ( i + 2 ) == 0 ) { maxPrime = i + 2 ; n = n / ( i + 2 ) ; } } if ( n > 4 ) maxPrime = n ; return maxPrime ; } int main ( ) { long long n = 15 ; cout << maxPrimeFactors ( n ) << endl ; n = 25698751364526 ; cout << maxPrimeFactors ( n ) ; }