How to calculate prime factors of a number in java / Prime factorization in java

What is a prime factor
A prime factor is made up of two terms : Factor and Prime Number.

A factor of a number is a number which completely divides the number. By completely divides, it means that the remainder of division is zero.
A prime number is a number which is only divisible by itself and 1. Examples of prime numbers are 2, 3, 5, 7, 11, 17, 29 etc.

Logic
Prime factors of a number can be calculated using the following steps:

1. Iterate over a loop using a counter starting from 2(since it is the smallest prime number) till the number.
2. In each iteration, divide the number by the current loop counter value and check the remainder. If the remainder is zero, the current value completely divides the number and is a factor of the number. Remainder is calculated using modulus operator(%) in java.
3. Determine the result of division of number by the digit by calculating the quotient of division. Quotient is calculated using division operator(/) in java.
4. If the current loop counter divides the number, we reduce it by 1(so that when it is incremented by the loop, it remains the same) since it is possible that same digit again divides the number completely.
   For Example, if the number is 44 and loop counter is 2, then in first iteration, the quotient comes out to be 44 / 2 = 22 which is again divisible by 2. If we increment the loop counter to 3, we will lose a factor.
5. Finally, the current loop counter is added to an ArrayList which contains all the factors of the number.

Program
Below code converts the above algorithm to a working program

import java.util.ArrayList;
import java.util.List;

public class PrimeFactorCalculator {

    public static List calculatePrimeFactors(int number) {
	int copyOfNumber = number;
	// initialize a list to contain all the factors
	List factors = new ArrayList();
	// loop from 2 till the number
	for (int currentNumber = 2; currentNumber < copyOfNumber; currentNumber++) {
		// check if the current loop counter completely divides the number
		if (copyOfNumber % currentNumber == 0) {
			// add it to list
			factors.add(currentNumber);
			// calculate quotient of division
			copyOfNumber /= currentNumber;
			// stop the number from incrementing in next iteration
			currentNumber--;
		}
	}
	return factors;
   }

   public static void main(String[] args) {
	System.out.println("Prime factors of 44");
	List primeFactors = calculatePrimeFactors(44);
	for (Integer factor : primeFactors) {
		System.out.println(factor);
	}
		
	System.out.println("Prime factors of 529");
	primeFactors = calculatePrimeFactors(44);
	for (Integer factor : primeFactors) {
		System.out.println(factor);
	}
   }
}

Output

Let's tweak in

1. If you want to calculate only unique prime factors of a number, replace the List by a Set or just add a contains check before adding the number to the list so that the number is only added to the list if it is not present in the list.
2. If you want to calculate the sum of all prime factors of a number, just declare a variable(sum for example) and initialize it to 0 and add each factor to this variable just before we are adding it to the list as sum += currentNumber.
3. For calculating the highest prime factor, declare a variable(highest for example) and initialize it to 0. In each iteration, compare the current factor with this variable.
   If the current factor is greater than this variable, replace it with current factor. At the end of the loop, this variable would have the largest factor.

Hit the clap below if you liked the post.