Lab 7: The Hidden Factor

Due by the end of class

The fundamental theorem of arithmetic states that any integer greater than one can be factored into a unique list of prime numbers (which might have only one element if the number is prime).

For example, the unique factorization of 60 is:

60 = 2 × 2 × 3 × 5 = 2² × 3 × 5

At this point in your programming career, it shouldn't be too hard for you to figure out how to print out such a factorization using a loop (probably a while). However, this lab requires you to print out the factorization with recursion!

Specification

Create a project called Lab7. Add a class called Factorizer.

The `main()` method

The main() method asks the user to enter a number to factorize and reads it in. If the number is greater than 1, it calls printFactorization() with the number and 2 as the initial factor. Otherwise, it merely prints Integers less than 2 do not have a prime factorization.

The `isPrime()` method

You must write an isPrime() method that returns true if its int argument is prime and false otherwise. Its signature should be as follows:

public static boolean isPrime(int number)

Although it is not efficient for truly large numbers, you can use the following algorithm to test whether number is prime. First, find its square root. Then, loop from 2 up to and including this square root. If the current loop variable evenly divides number, then number isn't prime, and you should return false. Once the loop has finished, none of the possible factors divided it; thus, number must be prime, and you can return true.

The `printFactorization()` method

The printFactorization() method is the interesting one, and it's also the one that's required to be recursive. In other words, it should contain no loops. Likewise, there's no reason for it to contain an assignment (using the = operator). Its signature should be as follows:

public static void printFactorization(int number, int factor)

This method doesn't divide itself into base cases and recursive cases as cleanly as some methods, but the following cases give a good outline of how to approach it.

Case 1: number is divisible by factor and factor is prime

Print factor
Case 1(a): number divided by factor is still greater than 1, meaning that there are more factors to find

Print out an asterisk with a space on either side
Make a recursive call with number divided by factor (the remaining material to be factored) and the current factor (since it might be a repeated factor)

Case 1(b): number divided by factor is not greater than 1, meaning that there are no more factors to find

Print out a newline to mark the ending of the factorization

Case 2: number is not divisible by factor or factor is not prime

Since the current value of factor isn't useful, make a recursive call with the current value of number and one more than the current value of factor

Although this method is not much less efficient than using loops, it is subject to stack overflow because the number of recursive calls can grow with the size of the number. Large prime numbers in particular (such as 15,485,863) will cause your program to crash. Don't worry about that for now. The goal now is merely to improve your skill at using recursion.

Sample Output

Here are three examples of sample output. In the first example, the user enters 60.

Enter number to factorize: 60
2 * 2 * 3 * 5

In the second example, the user enters 101, a prime number.

Enter number to factorize: 101
101

In the third example, the user enters 1, an illegal value.

Enter number to factorize: 1
Integers less than 2 do not have a prime factorization.

Turn In

Turn in your code by uploading Factorizer.java from the Lab7\src folder inside your workspace folder to Blackboard. Do not upload the entire project. I only want the Factorizer.java file.

All work must be done individually. Never look at someone else's code. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.