Support free tutorials:











vogella training Training Books



Prime Factorization - Algorithm in Java - Tutorial

Lars Vogel

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.


Table of Contents

1. Prime Factorization
2. Implementation in Java
2.1. A simple implementation
2.2. Performance optimized version
3. Support this website
3.1. Thank you
3.2. Questions and Discussion
4. Links and Literature
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) {
        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 .

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 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. Support this website

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.

3.1. Thank you

Please consider a contribution if this article helped you.

Flattr this

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

4. Links and Literature

4.1. Source Code

Source Code of Examples

4.2. General

Not listed yet