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)); } } |
|
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] |
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.
Was this post helpful?
Let us know if you liked the post. That’s the only way we can improve.
Further optimization can be done by running this loop till square root of input number.