Exercise: Prime Factorization

Write a program that finds the prime factors of a number. The prime factors of a number must satisfy the following conditions: For example, the prime factors of 12 are 2, 2, and 3, because: Another example, the prime factors of 210 are 2, 3, 5, and 7, because:

Finding prime factors

Using 44 as our example number, this is an algorithm to find its prime factors: This leaves use with the following prime factors for 44: 2, 2, and 11.

Example run

Consider this example code:
int[] numbers = { 2, 3, 4, 5, 6, 18, 27, 28, 210, 34251 };
for (int nr : numbers) {
  int[] factors = getPrimeFactors(nr);
  if (factors.length == 1) {
    System.out.println(nr + " is prime");
  } else {
    System.out.println("Prime factors of " + nr + ": " +
        toString(factors));
  }
}

Your program output should look like this:

2 is prime
3 is prime
Prime factors of 4: 2, 2
5 is prime
Prime factors of 6: 2, 3
Prime factors of 18: 2, 3, 3
Prime factors of 27: 3, 3, 3
Prime factors of 28: 2, 2, 7
Prime factors of 210: 2, 3, 5, 7
Prime factors of 34251: 3, 7, 7, 233
To check the correctness of your program, see this web application: Prime Factorization Calculator.

Hints 💡

You might write these methods to help you with your program:

Hand in instructions

  1. Make sure your program runs correctly.
  2. Hand in your program by uploading Main.java to Moodle.