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,3Lets create java program for it:

Run above program and you will get following output:

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.

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,3Lets create java program for it:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
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 primeFactors(int number) { int n = number; List primeFactors = new ArrayList(); 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:

1 2 3 4 5 6 7 8 |
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

1 2 3 4 5 6 7 8 9 10 |
// This method calculate prime factor and add it to primeFactor list public static List primeFactors(int number) { int n = number; List primeFactors = new ArrayList(); 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.

#### Join Our News Letter – Stay Updated

**Subscribe to Awesome Java Content**.

Further optimization can be done by running this loop till square root of input number.