How to Find Prime Factors of Integer Numbers in Java - Factorization Algorithm Example

One of the common homework/tasks in programming courses is about Prime Factorization. You are asked to write a program to find prime factors of a given integer number. The prime factors of a number are all of the prime numbers that will exactly divide the given number. For example, prime factors of 35 are 7 and 5, both are prime in themselves and exactly divide 35. The last time I did this exercise was when I was in college, and it was something like, writing a program that asks the user for an integer input and then displays that number's prime factorization on the command line.  

There are variants of this program as well e.g. look at this exercise, Write a program that prompts the user to enter a positive integer and displays all its smallest factors in decreasing order. It's more or less the same as the earlier mentioned version of the prime factorization problem, but with a catch of displaying them in decreasing order.

Displaying is not a problem at all, you can display it in a command prompt or a GUI easily, the main thing is to write logic to find prime factors, and this is what you will learn in this programming tutorial.

Remember, we can not use an API method, which directly solves the problem e.g. you are not allowed to use the reverse method of StringBuffer, in order to reverse a String in Java. 

You need to write the core logic of prime factorization by using primitive programming constructs e.g. control statements, loops, arithmetic operator, etc.

Though you can use essential functions e.g. length() to calculate the length of String or toArray() to convert String to array etc.

Java Program to Find Prime Factors

Without delaying any further here is our complete Java program to find prime factors. The logic of calculating prime factors are written inside method primeFactors(long number), it's a simple brute-force logic to find prime factors.

We start from 2, because that's the first prime number and every number is also divisible by 1, then we iterate until we find a prime factor by incrementing and stepping one at a time. 

When we find a prime factor, we store it inside a Set and also reduce the number till which we are looping.

In order to run this program, you can simply copy-paste it in a file PrimeFactors.java and then compile and run by using javac and java commands. 

If you find any difficulty running this program, you can also refer to this article for step by step guide on how to run a Java program from the command prompt.

import java.util.HashSet;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;

/**
* Java program to print prime factors of a number. For example if input is 15,
* then it should print 3 and 5, similarly if input is 30, then it should
* display 2, 3 and 5.
*
* @author Javin Paul
*/
public class PrimeFactors{

    public static void main(String args[]) {

        System.out.printf("Prime factors of number '%d' are : %s %n", 
                               35, primeFactors(35));
        System.out.printf("Prime factors of integer '%d' are : %s %n",
                               72, primeFactors(72));
        System.out.printf("Prime factors of positive number '%d' is : %s %n",
                               189, primeFactors(189));
        System.out.printf("Prime factors of number '%d' are as follows 
                               : %s %n",
                               232321, primeFactors(232321));
        System.out.printf("Prime factors of number '%d' are as follows
                               : %s %n",
                               67232321, primeFactors(67232321));

    }

    /**
     * @return prime factors of a positive integer in Java.
     * @input 40
     * @output 2, 5
     */
    public static Set<Integer> primeFactors(long number) {
        Set<Integer> primefactors = new HashSet<>();
        long copyOfInput = number;

        for (int i = 2; i &lt;= copyOfInput; i++) {
            if (copyOfInput % i == 0) {
                primefactors.add(i); // prime factor
                copyOfInput /= i;
                i--;
            }
        }
        return primefactors;
    }

}

Output:
Prime factors of number '35' are : [5, 7]
Prime factors of integer '72' are : [2, 3]
Prime factors of positive number '189' is : [3, 7]
Prime factors of number '232321' are as follows : [4943, 47]
Prime factors of number '67232321' are as follows : [12343, 419, 13]

If you are curious about what is that angle bracket <>, its diamond operator introduced in Java 7 for better type inference. Now you don't need to write type parameters in both side of expression, as you have to do in Java 1.6, this makes them more readable. 

Now coming back to exercise, if you look at the output, it only returns the unique prime factors because we are using Set interface, which doesn't allow duplicates.


If your Interviewer ask you to write program to divide a number into its prime factors, and print all of them, then you need to use List interface instead of Set. 

For example, unique prime factors of '72' are [2,3] but the number in terms of its prime factor is [2, 2, 2, 3, 3]. If you need that kind of output, you can rewrite our primeFactors(long number) method to return a List<Integer>, as shown below :

public static List<Integer> primeFactors(long number) {
        List<Integer> primefactors = new ArrayList<>();
        long copyOfInput = number;

        for (int i = 2; i <= copyOfInput; i++) {
            if (copyOfInput % i == 0) {
                primefactors.add(i); // prime factor
                copyOfInput /= i;
                i--;
            }
        }
        
        return primefactors;
    }

and, here is the output of running the same program with this version of primeFactors(long number) method. This time you can see all the prime factors instead of just the unique ones. This also explains the difference between the Set and List interface, a very important lesson for beginners.

Prime factors of number '35' are : [5, 7] 
Prime factors of integer '72' are : [2, 2, 2, 3, 3] 
Prime factors of positive number '189' is : [3, 3, 3, 7] 
Prime factors of number '232321' are as follows : [47, 4943] 
Prime factors of number '67232321' are as follows : [13, 419, 12343]

Now, its time to practice writing some JUnit tests. Actually, there are two ways to test your code, one is by writing main method, calling method and comparing actual output to expected output by yourself. Another, much more advanced and preferred approach is to use unit test framework like JUnit to do that.


If you follow test-driven development, then you can even write test before writing code and let test drive your design and coding. Let's see how our program fares with some JUnit testing.

import static org.junit.Assert.*;
import java.util.ArrayList;
import java.util.List;
import org.junit.Test;


public class PrimeFactorTest {

    private List<Integer> list(int... factors){
        List&lt;Integer&gt; listOfFactors = new ArrayList<>();
        
        for(int i : factors){
            listOfFactors.add(i);
        }       
        return listOfFactors;
    }
    
    @Test
    public void testOne() {
        assertEquals(list(), PrimeFactors.primeFactors(1));
    }
    
    @Test
    public void testTwo() {
        assertEquals(list(2), PrimeFactors.primeFactors(2));
    }

    @Test
    public void testThree() {
        assertEquals(list(3), PrimeFactors.primeFactors(3));
    }
    
    @Test
    public void testFour() {
        assertEquals(list(2,2), PrimeFactors.primeFactors(4));
    }
    
    @Test
    public void testSeventyTwo() {
        assertEquals(list(2,2,2,3,3), PrimeFactors.primeFactors(72));
    }
}

In our test class, PrimeFactorsTest we have five test cases to test corner cases, single prime factor cases, and multiple prime factor cases. We have also created a utility method list(int... ints) which takes advantage of Java 5 varargs to return a List of given numbers. 

You can call this method with any number of arguments including zero, in which case it will return an empty List. If you like, you can extend our test class to add few more tests e.g. performance tests, or some special case tests to test our prime factorization algorithm.

here is the output of our JUnit tests, if your new, you can also see this tutorial to learn how to create and run the JUnit test.

That's all about how to find prime factors of an Integer number in Java. Along with palindrome, Armstrong number and Sorting algorithms this is one of the common programming exercise which you can do to learn coding or improve your coding skills.

If you need more practice, you can also check out the following 20 programming exercises, ranging from various topics e.g. LinkedList, String, Array, Logic, and Concurrency.

1. How to Swap Two Numbers without using Temp Variable in Java? (Trick)
2. How to check if LinkedList contains loop in Java? (Solution)
3. Write a Program to Check if a number is Power of Two or not? (Answer)
4. How to find middle element of LinkedList in one pass? (See here for Solution)
5. How to check if a number is Prime or not? (Solution)
6. Write a Program to find Fibonacci Series of a Given Number? (Solution)
7. How to check if a number is Armstrong number or not? (Solution)
8. Write a Program to prevent Deadlock in Java? (Click here for solution)
9. Write a Program to solve Producer Consumer Problem in Java. (Solution)
10. How to reverse String in Java without using API methods? (Solution)
11. Write a Program to calculate factorial using recursion in Java? (Click here for solution)
12. How to check if a number is Palindrome or not? (Solution)
13. How to check if Array contains duplicate number or not? (Solution)
14. How to remove duplicates from ArrayList in Java? (Solution)
15. Write a Java Program to See if two String are Anagram of each other? (Solution)
16. How to count occurrences of  a character in String? (Solution)
17. How to find first non repeated characters from String in Java? (See here for solution)
18. Write a Program to check if a number is binary in Java? (Solution)
19. How to remove duplicates from array without using Collection API? (Solution)
20. Write a Program to calculate Sum of Digits of a number in Java? (Solution)

Now, now is the quiz time? What is the time and space complexity of this algorithm? Can you do better?