Related Tags

prime
factor
python
java
c++

# 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.

## Code

#include <iostream>
#include <vector>
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;

// vector to store all the prime factors of a number
vector<int>Factors;
// iterate from 2 to half of the number as there can be no factor
// greater than half of the number.
for(int i = 2; i <= number/2; i++)
{
//check if number is factor
if(number % i == 0)
{
// check if the factor is also a prime number
if(is_Prime(i)==true)
{
// add the value in the vector
Factors.push_back(i);
}
}
}
int max=1;
// iterate the vector to find largest prime factor
for(int i = 0; i < Factors.size(); i++)
{
if(Factors[i] > max)
{
max = Factors[i];
}
}

// output the largest prime factor
cout<<"Largest prime factor = " << max<<endl;
return 0;
}

For any number, we must first find out all the factors associated with it. For example, if we look at the number 15, we can see that it has three factors: 1,3,5. In the code, we run a loop from 2 to half of the number. In this case, the loop will run from 2 to 7. Now, we will check if 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.

RELATED TAGS

prime
factor
python
java
c++