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,2and3are prime numbers. As3is greater than2,3is said to be the largest prime factor of number6.
Code
#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.
RELATED TAGS
