Prime factors of a number. [Prime Factorization]

Question: Given an integer N, find all the prime factors of the number.

Input: N = 45

Output: 3 5

Finding prime factors of any numbers is a very important concept in number theory. One sample problem is available here in which we have to find the largest prime factor.

The mathematical concept behind this problem is simple. We start with ‘2’ and keep dividing the original number to get rid of composite factors. Continue this process until the number is no longer divisible by 2. This means that at this point, we do not have any multiples of 2 in the factors.

Example: 48 = 2 * 2 * 2 * 2 * 3
If we divide it by 2 four times we get rid of all the composite factors.

• Now we proceed with ‘3’ and so on to get rid of all the factors.
• Keep on adding these numbers to a set as they are left out.
• The reason these numbers are left out is because they are prime numbers.
• Hence, at the end of our loop we have all our prime factors in the set.

The code shown below implements the above algorithm.

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

public class PrimeFactorisation {

  /**
   * Created by studyalgorithms.com
   */

  public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);
    long N = scanner.nextLong();
    Set<Long> primeFactors = new HashSet<>();

    while (N % 2 == 0) {
      N /= 2;
      primeFactors.add(2L);
    }

    for (long j = 3; j <= Math.sqrt(N); j += 2) {
      while (N % j == 0) {
        N /= j;
        primeFactors.add(j);
      }
    }

    if (N > 2)
      primeFactors.add(N);

    for (Long primeFactor : primeFactors) {
      System.out.print(primeFactor + " ");
    }

  }
}
Code language: Java (java)

A working implementation of the code can be found here.