Prime Factorization in Java. This tutorial describes how to perform prime factorization of an integer with Java.
1. Prime Factorization
A prime is an integer greater than one those only positive divisors are one and itself. The prime factorization of an integer is the multiset of primes those product is the integer.
2. Implementation in Java
2.1. A simple implementation
Create a java project called de.vogella.algorithms.primefactors.
Create the following class.
package de.vogella.algorithms.primefactors;
import java.util.ArrayList;
import java.util.List;
public class PrimeFactors {
public static List<Integer> primeFactors(int number) {
int n = number;
List<Integer> factors = new ArrayList<Integer>();
for (int i = 2; i <= n; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
return factors;
}
public static void main(String[] args) {
System.out.println("Primefactors of 44");
for (Integer integer : primeFactors(44)) {
System.out.println(integer);
}
System.out.println("Primefactors of 3");
for (Integer integer : primeFactors(3)) {
System.out.println(integer);
}
System.out.println("Primefactors of 32");
for (Integer integer : primeFactors(32)) {
System.out.println(integer);
}
}
}You might be asking yourself why we just loop from 2 to n without checking if the iterator variable i is really a prime number. This is based on the fact that in the loop we have already tried to divide n by the values between 2 and i-1. Therefore i can only be a divisor of n if it is a prime, otherwise we would have found a fitting divisor already in the loop between 2 and i-1.
2.2. Performance optimized version
A more effective implementation of the Prime Factorization is implemented in the following class.
package de.vogella.algorithms.primefactors;
import java.util.ArrayList;
import java.util.List;
public class PrimeFactorsEffective {
public static List<Integer> primeFactors(int numbers) {
int n = numbers;
List<Integer> factors = new ArrayList<Integer>();
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) {
factors.add(n);
}
return factors;
}
public static void main(String[] args) {
System.out.println("Primefactors of 44");
for (Integer integer : primeFactors(44)) {
System.out.println(integer);
}
System.out.println("Primefactors of 3");
for (Integer integer : primeFactors(3)) {
System.out.println(integer);
}
System.out.println("Primefactors of 32");
for (Integer integer : primeFactors(32)) {
System.out.println(integer);
}
}
}This uses the fact that, if we know that a loop i n has no divisors less or equal than i (which was explained earlier) it can also not have a divisor which is larger than n/i.
3. Links and Literature
Nothing listed.
3.1. vogella Java example code
If you need more assistance we offer Online Training and Onsite training as well as consulting