In this article we will see how to find prime factors of a given Number, a prime number is a whole number greater than 1 whose only factors are 1 and itself.

Input: 1
Output: [1]

Input: 17
Output: [17]

Input: 215
Output: [5,43]

Prime factorisation means finding all the factors of a given number where each of these factors must be a prime number. There is only one unique set of prime factors for a given number. We can find the solution with following steps:

1) Divide the number by 2 until it's completely divisible, add 2 as a factor.
2) Now the number must be an odd number, starts a loop from 3 to Square Root of the number, if the number is completly divisible by i add i as a factor. We can increment i by 2 because of n being an odd number.
3) In case the number tested is a prime number above two steps will not produce any factor and n will never be 1, add the number to factors if greater than 2.

package com.tb.array;

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

public class PrimeFactors {

 /*
  * Return prime factors of a given number n
  */
 private static List primeFactors(int n) {
  List factors = new ArrayList();
  if (n    factors.add(n);
   return factors;
  }

  while (n % 2 == 0) {
   factors.add(2);
   n = n / 2;
  }

  for (int i = 3; i    if (n % i == 0) {
    factors.add(i);
    n = n / i;
   }
  }

  if (n > 2)
   factors.add(n);

  return factors;

 }

 public static void main(String[] args) {
  System.out.println(primeFactors(1));
  System.out.println(primeFactors(2));
  System.out.println(primeFactors(3));
  System.out.println(primeFactors(12));
  System.out.println(primeFactors(17));
  System.out.println(primeFactors(215));

 }

}

Output: Above code will print something like this on console.

[1]
[2]
[3]
[2, 2, 3]
[17]
[5, 43]

This program finds all prime factors of a given number, if you have some better way to solve this logical problem please share your thoughts in comments below.