Largest prime factor

The Largest prime factor is a very simple concept. Let’s break it down:

  • Every number has many different factors.
  • Factors are numbers that completely divide a particular number to get zero as a remainder.
  • For example, if we look at the number 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.
svg viewer

Code

#include <iostream>
using namespace std;
bool is_Prime(int x)
{
// invalid input
if (x <= 1)
return false;
// process all potential divisors
for(int i = 2; i <= x / 2; i++) {
if(x % i == 0) {
return false;
}
}
// no divisor found, therfore it's a prime number
return true;
}
int main() {
// the number we want factors of
int 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 factor
if(number % i == 0)
{
// check if the factor is also a prime number
if(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.

Copyright ©2024 Educative, Inc. All rights reserved