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,3Lets 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 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:

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.