## Prime Factorization - Algorithm in Java - Tutorial

Version 1.1

04.02.2013

Prime Factorization in Java

This tutorial describes how to perform prime factorization of an integer with Java.

1. Prime Factorization
2. Implementation in Java
2.1. A simple implementation
2.2. Performance optimized version
3.1. Donate to support free tutorials
3.2. Questions and discussion
3.3. License for this tutorial and its code
4.1. Source Code
4.2. General

## 1. Prime Factorization

A prime is an integer greater then 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) {
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 ask yourself my we just looping from 2 to n without checking if the iterator variable i is really a prime number. This is based on the fact that a any 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) {
n /= i;
}
}
if (n > 1) {
}
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 now that a loop i n has no divisors less then or equal then i (which I have explained earlier) it can also not have a divisor which is larger then n/i.

### 3.1. Donate to support free tutorials

Please consider a contribution if this article helped you. It will help to maintain our content and our Open Source activities.

### 3.2. Questions and discussion

Writing and updating these tutorials is a lot of work. If this free community service was helpful, you can support the cause by giving a tip as well as reporting typos and factual errors.

If you find errors in this tutorial, please notify me (see the top of the page). Please note that due to the high volume of feedback I receive, I cannot answer questions to your implementation. Ensure you have read the vogella FAQ as I don't respond to questions already answered there.

### 3.3. License for this tutorial and its code

This tutorial is Open Content under the CC BY-NC-SA 3.0 DE license. Source code in this tutorial is distributed under the Eclipse Public License. See the vogella License page for details on the terms of reuse.

Not listed yet