Question

How to find the largest prime factor of a number in C++

Answer 1

#include <iostream>

int largestPrimeFactor(int n) {
    int div = 2, maxPFact = -1;
    while (n != 0) {
        if (n % div != 0)
            div = div + 1;
        else {
            maxPFact = n;
            n = n / div;
            if (n == 1) {
                break;
            }
        }
    }
    return maxPFact;
}

int main() {
    int n = 124;
      
    std::cout << largestPrimeFactor(n) << "\n"; // 2 x 2 x 31
    std::cout << largestPrimeFactor(288) << "\n"; // 2 x 2 x 2 x 2 x 2 x 3 x 3
    std::cout << largestPrimeFactor(1288) << "\n"; // 2 x 2 x 2 x 7 x 23
}



/*
run:

31
3
23

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>

// Function to return the largest prime factor of n
long long largestPrimeFactor(long long n) {
    long long largest = -1;

    // Remove all factors of 2
    while (n % 2 == 0) {
        largest = 2;
        n /= 2;
    }

    // Check odd factors from 3 to sqrt(n)
    for (long long i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            largest = i;
            n /= i;
        }
    }

    // If n is still > 2, it is prime
    if (n > 2)
        largest = n;

    return largest;
}

int main() {
    int n = 124;
    std::cout << largestPrimeFactor(n) << "\n";       // 2 x 2 x 31

    std::cout << largestPrimeFactor(288) << "\n";     // 2 x 2 x 2 x 2 x 2 x 3 x 3

    std::cout << largestPrimeFactor(1288) << "\n";    // 2 x 2 x 2 x 7 x 23

    std::cout << largestPrimeFactor(100000000) << "\n"; // 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5 x 5 x 5 x 5 x 5

    long long ln = 600851475143;
    std::cout << "Largest prime factor: "
         << largestPrimeFactor(ln) << "\n";      // 71 x 839 x 1471 x 6857
}



/*
run:
     
31
3
23
5
Largest prime factor: 6857
     
*/

 

70+ SQL courses for beginners and professionals