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:
- They must be prime numbers.
- They must multiply together to give the original number.
For example, the prime factors of 12 are 2, 2, and 3, because:
- 2 and 3 are prime.
- 2 * 2 * 3 = 12.
Another example, the prime factors of 210 are 2, 3, 5, and 7, because:
- 2, 3, 5, and 7 are prime.
- 2 * 3 * 5 * 7 = 210.
Finding prime factors
Using 44 as our example number, this is an algorithm to find its prime factors:
- Start with the smallest prime, 2
- Check if 2 is a factor of 44. Yes, it is, so we can divide 44 by 2 to get 22.
- Continue using 2 as the factor: Check if 2 is a factor of 22. Yes, our new number is 11.
- 11 is not divisible by 2, so we move to the next possible factor, which is 3.
- Check if 3 is a factor of 11. No, it isn't, so we move to the next possible factor, 4.
- 4 is also not a factor of 11
- Continue like this till we reach 11 as our possible factor. 11 is prime and is of course a factor of 11.
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:
- Gets the prime factors of a number as an array:
int[] getPrimeFactors(int nr)
- Turns an
int
array into a string: String toString(int[] arr)
- Creates a new array that's a copy of the input array but without trailing zeros:
int[] rightTrim(int[] arr)
Hand in instructions
- Make sure your program runs correctly.
- Hand in your program by uploading Main.java to Moodle.