Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

prime
factor
python
java
c++

Largest prime factor

Educative Answers Team

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>
#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++
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring