Tutorial

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 "de.vogella.algorithms.primefactors".

Create the following program.

			
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) {
		for (Integer integer : primeFactors(44)) {
			System.out.println(integer);
		}
		for (Integer integer : primeFactors(3)) {
			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 the following.

			
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) {
		for (Integer integer : primeFactors(44)) {
			System.out.println(integer);
		}
		for (Integer integer : primeFactors(3)) {
			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.

Please help me to support this article:

Before posting questions, please see the vogella FAQ. If you have questions or find an error in this article please use the www.vogella.de Google Group. I have created a short list how to create good questions which might also help you.