Home Tutorials Training Consulting Products Books Company Donate Contact us









Online training

Events

Quick links

Share

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

1. Prime Factorization

A prime is an integer greater than 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 be asking yourself why we just loop from 2 to n without checking if the iterator variable i is really a prime number. This is based on the fact that in the 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 know that a loop i n has no divisors less or equal than i (which was explained earlier) it can also not have a divisor which is larger than n/i.

3. Links and Literature

Nothing listed.

4. vogella training and consulting support

Copyright © 2012-2018 vogella GmbH. Free use of the software examples is granted under the terms of the Eclipse Public License 2.0. This tutorial is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Germany license.