How to find Largest Prime Factor of a Number in Java - Programming Kata

One of the common programming kata to learn coding is write a program to find the largest prime factor of a number. Like any other programming problem, you need to build the logic to solve this problem. Before solving the problem, let's revise the concept of number theory. Prime factors of a positive integer are the prime numbers that divide the number exactly i.e. without any remainder, and prime factorization is the process of finding all prime numbers when multiply together make original number.  A positive integer can have multiple prime factors, our challenge is to find the largest prime factor of a number. For example, 6 has two prime factors 2 and 3, your program should return 3, because that's the largest prime factors. In one of earlier problem, we have learned how to find prime factor of a number in Java and we will use the similar logic here, but instead of returning a list of prime factors we will only return the largest prime factor.

Java Program to Find Largest Prime Factor of an Integer

Problem : Write a program to find the largest prime factor of a positive integer in Java. If we pass 15 to your program, it should return 5, and if we pass 6 to your program it should return 3.

Solution : As we learned a number is called prime factor if it is prime number and it can divide the number exactly. Another property of prime factor is that if we keep dividing the number by prime factor then it will either fully divide the number or produce another prime factor e.g. if we need to find the prime factors of 16 then starting from 2 if keep dividing, eventually dividend become 1, so 2 is the only prime factor of 16. On other hand if need to find prime factor of 15, then we first try to divide it by 2, but since its not divisible by 2, we move to next number which is 3. Since 3 can divide 15, it produces another prime number 5, now 5 is not divisible by anything other than 5, so 3 and 5 become prime factor of 15.

Algorithm : In our program, we have used the same logic. We start with 2, the smallest prime number and try to divide the number, if number is divisible then we keep dividing it by same number until its not divisible any more. Now we move to next number, the largest number which is able to fully divide the input is our largest prime factor. This would be more clear when you see the actual program.

import java.util.Random;
import java.util.Scanner;

/**
* Java program to find and print largest prime factor of an integer number. for
* example number 6 has two prime factors 2 and 3, but 3 is the largest prime
* factor of 6. input 15 output 5
*
* @author Javin Paul
*/
public class LargetPrimeFactor{

    public static void main(String args[]) {

        System.out.printf("Largest prime factor of number '%d' is %d %n",
                6, largestPrimeFactor(6));
        System.out.printf("highest prime factor of number '%d' is %d %n",
                15, largestPrimeFactor(15));
        System.out.printf("Biggest prime factor of number '%d' is %d %n",
                392832, largestPrimeFactor(392832));
        System.out.printf("Largest prime factor of number '%d' is %d %n",
                1787866, largestPrimeFactor(1787866));
    }

    /**
     * @return largest prime factor of a number
     */
    public static int largestPrimeFactor(long number) {
        int i;
        long copyOfInput = number;

        for (i = 2; i <= copyOfInput; i++) {
            if (copyOfInput % i == 0) {
                copyOfInput /= i;
                i--;
            }
        }

        return i;
    }

}

Output:
Largest prime factor of number '6' is 3
highest prime factor of number '15' is 5
Biggest prime factor of number '392832' is 31
Largest prime factor of number '1787866' is 893933

You can see from output that our program is working properly, for 6 the largest prime factor is 3 and for 15 its 5. Here is our unit test to check couple of more numbers :

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class LargestPrimeFactorTest {
    
   
    @Test
    public void testLargestPrimeFactors(){
        assertEquals(2, HelloWorld.largestPrimeFactor(2));
        assertEquals(3, HelloWorld.largestPrimeFactor(6));
        assertEquals(5, HelloWorld.largestPrimeFactor(15));
        assertEquals(7, HelloWorld.largestPrimeFactor(147));
        assertEquals(17, HelloWorld.largestPrimeFactor(17));
        assertEquals(31, HelloWorld.largestPrimeFactor(392832));
        assertEquals(893933, HelloWorld.largestPrimeFactor(1787866));
    }    
    
}

and here is the test result, you can see the test passed successfully.

One thing to note here is that we are not handling invalid input here e.g. 0, 1 or negative number, which we should if this question is asked on Interview. You can throw IllegalArgumentException for those inputs which are not valid as per problem specification. Similarly, you also need to include unit test to check those invalid inputs. I leave that task for you as practice.


That's all about how to find largest prime factor of a number in Java. This is a really good exercise to learn coding when you are starting with Java or Python or any other programming language. This kind of problem will help to build your programming logic and improve your coding skill. Believe me, its not easy to convert a real life algorithm into program without practice. You must solve some basic coding problem based upon String, array and recursion to get hold of coding. I have shared many such exercise in this blog, if you are interested you can also take a look at following list of problem :

• How to Swap Two Numbers without using Temp Variable in Java? (Trick)
• Write a program to check if LinkedList contains loop in Java? (Solution)
• How to remove duplicates from array without using Collection API? (Solution)
• How to calculate Sum of Digits of a number in Java? (Solution)
• Write a Program to Check if a number is Power of Two or not? (Answer)
• Write a function to find middle element of LinkedList in one pass? (See here for Solution)
• How to find first non repeated characters from String in Java? (See here for solution)
• How to check if a number is binary in Java? (Solution)
• Write a program to check if a number is Prime or not? (Solution)
• How to find Fibonacci Series of a Given Number? (Solution)
• Write a method to check if two String are Anagram of each other? (Solution)
• Write a method to count occurrences of  a character in String? (Solution)
• How to check if a number is Armstrong number or not? (Solution)
• Write a method to remove duplicates from ArrayList in Java? (Solution)
• How to prevent Deadlock in Java? (Click here for solution)
• Howto solve Producer Consumer Problem in Java. (Solution)
• Write a program to check if a number is Palindrome or not? (Solution)
• Write a program to check if Array contains duplicate number or not? (Solution)
• How to reverse String in Java without using API methods? (Solution)
• How to calculate factorial using recursion in Java? (Click here for solution)