Write a program to find the largest prime factor of a number in C/CPP

Write a program to find the largest prime factor of a number in C/CPP.

Algorithm:

1. Initialize a variable largestFactor to 1, which will store the largest prime factor found so far.
2. Check if the number is divisible by 2, and if it is, divide the number by 2 and update largestFactor to 2. Repeat this step until the number is no longer divisible by 2.
3. Starting from 3, and incrementing by 2 each time, iterate through all the odd numbers less than or equal to the square root of the number.
4. For each number in the iteration check if it divides the number completely, if it does, divide the number by the current number and update largestFactor to the current number. Repeat this step until the number is no longer divisible by the current number.
5. Check if the number is greater than 2, if it is, update largestFactor to the number.
6. Return largestFactor as the largest prime factor of the given number.

Coding:

#include <iostream>
using namespace std;
 
int largestPrimeFactor(int n) {
    int largestFactor = 1;
    while (n % 2 == 0) {
        largestFactor = 2;
        n = n/2;
    }
 
    for (int i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0) {
            largestFactor = i;
            n = n/i;
        }
    }
    if (n > 2) {
        largestFactor = n;
    }
    return largestFactor;
}
 
int main() {
    int n;
    cin >> n;
    cout << "Largest Prime Factor of " << n << " is " << largestPrimeFactor(n) << endl;
    return 0;
}


#HappyProgramming
#HappyCoding