Version 1.1

Copyright © 2009, 2010, 2011, 2012 Lars Vogel

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 |

**Table of Contents**

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.

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 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 .

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 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.

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.

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.

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

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.