Trusted answers to developer questions

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`

.

#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

Related Courses