The Largest prime factor is a very simple concept. Let’s break it down:
6
, it has four factors: 1
,2
,3
,6
. However, of these factors, 2
and 3
are prime numbers. As 3
is greater than 2
, 3
is said to be the largest prime factor of number 6
.#include <iostream>using namespace std;bool is_Prime(int x){// invalid inputif (x <= 1)return false;// process all potential divisorsfor(int i = 2; i <= x / 2; i++) {if(x % i == 0) {return false;}}// no divisor found, therfore it's a prime numberreturn true;}int main() {// the number we want factors ofint number = 123;// iterate from half of the number to 2 as there can be no factor// greater than half of the number.for(int i = number/2; i >= 2; i--){//check if number is factorif(number % i == 0){// check if the factor is also a prime numberif(is_Prime(i))cout<<"Largest prime factor = " << i<<endl;break;}}return 0;}
Explanation: For any number, we must first find out all the factors associated with it. For example, if we look at the number 123
, we can see that it has two factors: 41
and ,3
. In the code, we run a loop from number/2
to 2
.(If we run the reverse loop we will find the largest factor first without the hassle to check the smaller ones first). In this case, the loop will run from 61
to 2
. Now, we will check if this i
is a factor of the given number. If it is a factor then we will check each factor is also a prime number. We have defined a helper function in the code to check if a number is prime or not – we call this function on every factor. If the number is a factor and also a prime, we add it to the maintained list of factors. At last, we find out the maximum number from the list to obtain the largest prime factor.