How to calculate prime factors of a number in java / Java program to calculate prime factors of a number

What is a prime factor

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

Prime Factor  = Factor + 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

Prime factors of 44
2
2
11
Prime factors of 529
2
2
11

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.