Lab #7: Factoring

The goal of this lab is to write a class Factoring for computing the prime factorization of an integer N >= 2 received from the user. The prime factoring of an integer N is the series of prime numbers in the nondecreasing order whose product is equals to N. Here are some examples of prime factorization:

N = 101: 101
N = 102: 2 * 3 * 17
N = 103: 103
N = 104: 2 * 2 * 2 * 13
N = 143: 11 * 13
N = 144: 2 * 2 * 2 * 2 * 3 * 3
N = 169: 13 * 13

If a prime divides N more than once, the number of times that the prime divides N can be presented as an exponent, as in:

N = 101: 101
N = 102: 2 * 3 * 17
N = 103: 103
N = 104: 2^3 * 13
N = 143: 11 * 13
N = 144: 2^4 * 3^2
N = 169: 13^2

The prime factorization of an integer N can be found dynamically using an algorithm that searches for prime factors in increasing order and, when a prime factor is found, reduces N by dividing the prime factor as many times as possible. More precisely, we can use the following algorithm:

1. Use two long variables, theQuotient and theDivisor. The variable theQuotient is for storing the value of the input after some or no divisions have been made on the input and the variable theDivisor is for storing the current factor to be considered. Initially set theQuotient to the input and theDivisor to 2.
2. While theQuotient is greater than 1, do the following:
   1. If theDivisor does not divide theQuotient, increase theDivisor by 1.
   2. Otherwise, while theDivisor divides theQuotient, keep reducing theQuotient by dividing it by theDivisor.

Suppose N is the input and P is a prime factor of N (P may be N itself). We can argue that the following properties hold:

1. Since P has no factor >= 2 other than P itself, the fact that P divides N will not be discovered while theDivisor is less than P, and so, when theDivisor reaches P, theQuotient must be divisible by P and the number of times N is divisible by theDivisior is equal to the number of times the value of the theDivisor at that point is divisible by theDivisor.
2. Thus, once theDivisor becomes > P, theQuotient is no longer divisble by P.

This argument applies not only to N and its prime factor P but also all the values of theDivisor and its prime factor at the start of Step 2a.

From this we can conclude that if the algorithm finds that the value of theDivisor divides theQuotient, it must be the case that the value is prime, and so, the algorithm discovers all the prime factors of N in the increasing order. In particular, if theQuotient is prime, its divisor (theQuotient itself) is found when theDivisor is increased theQuotient.

Each of the two different output formats of prime factorization can be generated by implementing this algorithm and by adding a component to produce the output. In the first format, we have only to produce an asterisk before printing the prime factor, but that asterisk sign is not needed if theQuotient is equal to the input N. In the second format, instead of printing each prime factor, we compute the number of times the prime factor that has been found divides theQuotient and prints the count after a caret (‘^’) if the number is greater than or equal to 2.

Here is an example execution:

% java Factoring
Enter number (enter 0 to quit): 300
300 = 2 * 2 * 3 * 5 * 5
300 = 2^2 * 3 * 5^2
Enter number (enter 0 to quit): 81
81 = 3 * 3 * 3 * 3
81 = 3^4
Enter number (enter 0 to quit): 34537
34537 = 34537
34537 = 34537
Enter number (enter 0 to quit): 0

You may use this template: Factoring.java

Go back to the lab main page

Go back to the home page