NOW Hiring

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 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 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 then i (which was explained earlier) it can also not have a divisor which is larger then n/i.

3. About this website

4. Links and Literature

4.1. Source Code

Not listed yet.

4.3. vogella GmbH training and consulting support

TRAINING SERVICE & SUPPORT

The vogella company provides comprehensive training and education services from experts in the areas of Eclipse RCP, Android, Git, Java, Gradle and Spring. We offer both public and inhouse training. Whichever course you decide to take, you are guaranteed to experience what many before you refer to as “The best IT class I have ever attended”.

The vogella company offers expert consulting services, development support and coaching. Our customers range from Fortune 100 corporations to individual developers.

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

See Licence.