Question

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

Answer 1

#include <stdio.h>
   
int largestPrimeFactor(long 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;
      
    printf("%d\n", largestPrimeFactor(n)); // 2 x 2 x 31
    printf("%d\n", largestPrimeFactor(288)); // 2 x 2 x 2 x 2 x 2 x 3 x 3
    printf("%d\n", largestPrimeFactor(1288)); // 2 x 2 x 2 x 7 x 23
    printf("%d\n", largestPrimeFactor(100000000)); // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 
    
    return 0; 
}
   
   
    
    
    
/*
run:
    
31
3
23
5
    
*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <stdio.h>

long long largestPrimeFactor(long long n) {
    long long maxPrime = -1;

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

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

    // If n is now > 2, it is prime
    if (n > 2)
        maxPrime = n;

    return maxPrime;
}

int main() {
    int n = 124;
    
    printf("%d\n", largestPrimeFactor(n)); // 2 x 2 x 31
    printf("%d\n", largestPrimeFactor(288)); // 2 x 2 x 2 x 2 x 2 x 3 x 3
    printf("%d\n", largestPrimeFactor(1288)); // 2 x 2 x 2 x 7 x 23
    printf("%d\n", largestPrimeFactor(100000000)); // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 
    
    long long ln = 600851475143; 
    printf("Largest prime factor: %lld\n", largestPrimeFactor(ln)); // 71, 893, 1471, 6857

    return 0;
}


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

 

70+ SQL courses for beginners and professionals

Answer 3

#include <stdio.h>

long largestPrimeFactor(long n) {
    long div = 2;
    long maxPFact = -1;

    while (n > 1) {
        if (n % div == 0) {
            maxPFact = div;
            n /= div;
        } else {
            div++;
        }
    }

    return maxPFact;
}

int main() {
    int n = 124;
    
    printf("%d\n", largestPrimeFactor(n)); // 2 x 2 x 31
    printf("%d\n", largestPrimeFactor(12)); // 2 x 2 x 3
    printf("%d\n", largestPrimeFactor(288)); // 2 x 2 x 2 x 2 x 2 x 3 x 3
    printf("%d\n", largestPrimeFactor(1288)); // 2 x 2 x 2 x 7 x 23
    printf("%d\n", largestPrimeFactor(100000000)); // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 
    
    long long ln = 600851475143; 
    printf("Largest prime factor: %lld\n", largestPrimeFactor(ln)); // 71, 893, 1471, 6857

    return 0;
}



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

 

70+ SQL courses for beginners and professionals