How to find prime factors of a number in java

In this post, we will see how to find prime factors of a number in java.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
The prime factors of a number are all of the prime numbers that will exactly divide the given number.
For example-
Prime factor of 15 = 3,5
Prime factor of 48=2,2,2,2,3

Lets create java program for it:
package org.arpit.java2blog;

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

public class PrimeFactorsMain {

 // This method calculate prime factor and add it to primeFactor list
 public static List<Integer> primeFactors(int number) {
  int n = number;
  List<Integer> primeFactors = new ArrayList<Integer>();
  for (int i = 2; i <= n; i++) {
   while (n % i == 0) {
    primeFactors.add(i);
    n /= i;
   }
  }
  return primeFactors;
 }

 public static void main(String[] args) {
  System.out.println("Primefactors of 15 are : ");
  System.out.printf("%s %n",primeFactors(15));

  System.out.println("Primefactors of 48 are :");
  System.out.printf("%s %n",primeFactors(48));

  System.out.println("Primefactors of 91");
  System.out.printf("%s %n",primeFactors(91));

 }
} 
Run above program and you will get following output:
Primefactors of 15 are : 
[3, 5] 
Primefactors of 48 are :
[2, 2, 2, 2, 3] 
Primefactors of 91
[7, 13] 
You must be wondering we are not checking whether loop variable i is prime or not But you don't need to do this because in any loop, number has been already divided by 2 to i-1 so i can only be divisor if it is prime.

More optimized solution:

Change above primeFactors function to below function
 // This method calculate prime factor and add it to primeFactor list
 public static List<Integer> primeFactors(int number) {
  int n = number;
  List<Integer> primeFactors = new ArrayList<Integer>();
  for (int i = 2; i <= n/i; i++) {
   while (n % i == 0) {
    primeFactors.add(i);
    n /= i;
   }
  }
  if(n>1)
   primeFactors.add(n);
  return primeFactors;
 } 
This is based on the fact that in above for loop,divisor can not be greater than n/i.

Please go through java interview programs for more such programs.

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012