## Prime Factorization - Algorithm in Java

Version 1.1

04.02.2013

Revision History
Revision 0.1 17.05.2009 Lars
Vogel
Created
Revision 0.2 - 1.1 02.06.2009 - 04.02.2013 Lars
Vogel
bugfixes and enhancements

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. Thank you
4. Questions and Discussion
5.1. Source Code
5.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.

## 4. Questions and Discussion

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.

Not listed yet