Question

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

Answer 1

public class MyClass {
    public static long largestPrimeFactor(long n) {
        long 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;
    }
    public static void main(String args[]) {
        int n = 124;
          
        System.out.println(largestPrimeFactor(n)); // 2 x 2 x 31
        System.out.println(largestPrimeFactor(288)); // 2 x 2 x 2 x 2 x 2 x 3 x 3
        System.out.println(largestPrimeFactor(1288)); // 2 x 2 x 2 x 7 x 23
        System.out.println(largestPrimeFactor(100000000)); // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 
    }
}
   
   
   
   
/*
run:
   
31
3
23
5

*/

 

70+ SQL courses for beginners and professionals

Answer 2

public class Main {

    // Returns the largest prime factor of n
    public static long largestPrimeFactor(long n) {

        long largest = -1;

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

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

        // Step 3: If n is still > 2, it is a prime number
        if (n > 2) {
            largest = n;
        }

        return largest;
    }

    public static void main(String[] args) {

        int n1 = 124; // 2 x 2 x 31
        int n2 = 288; // 2 x 2 x 2 x 2 x 2 x 3 x 3
        int n3 = 1288; // 2 x 2 x 2 x 7 x 23
        int n4 = 100000000; // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
        long n5 = 600851475143L; // 71, 839, 1471, 6857

        System.out.println("Largest prime factor: " + largestPrimeFactor(n1));
        System.out.println("Largest prime factor: " + largestPrimeFactor(n2));
        System.out.println("Largest prime factor: " + largestPrimeFactor(n3));
        System.out.println("Largest prime factor: " + largestPrimeFactor(n4));
        System.out.println("Largest prime factor: " + largestPrimeFactor(n5));
    }
}



/*
run:

Largest prime factor: 31
Largest prime factor: 3
Largest prime factor: 23
Largest prime factor: 5
Largest prime factor: 6857

*/

 

70+ SQL courses for beginners and professionals