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.

http://www.vogella.com/code/codejava.html Source Code of Examples