[Solved] How to find Largest Prime Factor of a Number in Java? Example

Hello guys, one of the common programming kata to learn coding is to write a program to find the largest prime factor of a number. Earlier, we have solved how to check if number is prime or not and in this article, we will calculate prime factors of a given number in Java.  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 multiplied together to make the 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 factor.

In one of the earlier problems, we have learned how to find the prime factors of a number in Java and we will use a similar logic here, but instead of returning a list of prime factors, we will only return the largest prime factor.

Also, basic knowledge of essential data structure and algorithms is also very important and that's why I suggest all Java programmers join these best Data Structure and Algorithms courses to improve their data structure knowledge and algorithms skills.

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 a prime factor if it is a 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.

For example, if you 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 the other hand, if we need to find a prime factor of 15, then we first try to divide it by 2, but since its not divisible by 2, we move to the 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 a prime factors 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 the number is divisible then we keep dividing it by same number until its not divisible anymore. 

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 the 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 a 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 numbers, 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 tests to check those invalid inputs. I leave that task for you as practice.


That's all about how to find the largest prime factor of a number in Java. This is a really good exercise to learn to code 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, it's not easy to convert a real-life algorithm into a program without practice.


More Java Coding Problems for Practice
You must solve some basic coding problems based upon String, array, and recursion to get hold of coding. I have shared many such exercises in this blog, if you are interested you can also take a look at the following list of problems:

• How to Swap Two Numbers without using Temp Variable in Java? (Trick)
• Write a program to check if LinkedList contains a loop in Java? (Solution)
• How to remove duplicates from the 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 the middle element of LinkedList in one pass? (See here for Solution)
• How to find the 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 an 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)
• How to 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)

Thanks for reading this article, if you have any questions or doubt feel free to ask on comments and lastly one question for you, what was the last coding question you were asked on interview? Was it simple or tough? do let us know in comments.