Solution for
Programming Exercise 3.2
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 3.2:
Which integer between 1 and 10000 has the largest number of divisors,
and how many divisors does it have? Write a program to find the
answers and print out the results. It is possible that several
integers in this range have the same, maximum number of divisors.
Your program only has to print out one of them.
One of the examples from Section 3.4
discussed divisors. The source code for that example is
CountDivisors.java.
You might need some hints about how to find a maximum value.
The basic idea is to go through all the integers, keeping track of
the largest number of divisors that you've seen so far.
Also, keep track of the integer that had that number of divisors.
Discussion
Let's use a variable named maxDivisors to keep track of
the largest number of divisors we have seen so far and use numWithMax
to store the number that had that many divisors. We have to compute
the number of divisors of each integer from 1 to 10000.
Whenever we find a larger number of divisors than maxDivisors,
we have to make note of that fact by changing the values of maxDivisors
and numWithMax. At the end of the process, maxDivisors
will be the absolute maximum number of divisors and numWithMax
will be a number that had that many divisors. These are the values
we want to print out. We can express this with a pseudocode algorithm
for each integer N from 1 to 10000:
Count the number of divisors of N
If that number is greater than maxDivisors:
Let maxDivisors = the number of divisors of N
Let numWithMax = N
Output maxDivisors and numWithMax
However, there is a problem here: The very first time maxDivisors
is used in the test "If that number is greater than maxDivisors,"
the variable
maxDivisors hasn't yet been assigned a value. The computer will report this as
an error. This can be fixed by assigning a value to maxDivisors
before the beginning of the for loop. One way to do this is
to handle N=1 as a special case before the loop and then to
let N go from 2 to 10000 in the for loop. We know
that N=1 has just 1 divisor:
Let maxDivisors = 1 // number of divisors of 1
Let numWithMax = 1
for each integer N from 2 to 10000:
Count the number of divisors of N
If that number is greater than maxDivisors:
Let maxDivisors = the number of divisors of N
Let numWithMax = N
Output maxDivisors and numWithMax
Here's a curious thing: If you leave out the line "numWithMax = 1"
from the program, the computer will report a syntax error where you
try to output the value of numWithMax. It will say that the
variable numWithMax might not have been initialized. That is,
it might never have been assigned a value. Now, you
know that it will be assigned a value (since when N=2 is processed,
numWithMax will become 2). However, when the computer compiles the
program, it doesn't know whether the body of the if
statement will ever be executed, so it doesn't know whether numWithMax
will ever be assigned a value. The syntax rule
is that every variable must be "definitely initialized" before
its value is used. This means that it is initialized on every possible
execution path through the program.
We still have to expand the step "Count the number of divisors of N."
This was already done in Section 3.4 for the example program CountDivisors.java.
This step requires another for loop, so we have here an example
of one for loop nested inside another. Here is a complete
algorithm, which can be translated into a program:
Let maxDivisors = 1 // number of divisors of 1
Let numWithMax = 1
for each integer N from 2 to 10000:
Let divisorCount = 0
for each D from 1 to N:
if D is a divisor of N:
add 1 to divisorCount
If divisorCount is greater than maxDivisors:
Let maxDivisors = the number of divisors of N
Let numWithMax = N
Output maxDivisors and numWithMax
This can be translated pretty much directly into a program.
By the way, the maximum number of divisors is 64. There are two numbers
between 1 and 10000 that have 64 divisors, 7560 and 9240. The
program will output the first of these. (It would output the
second if the test "if (divisorCount > maxDivisors)"
were changed to "if (divisorCount >= maxDivisors)".
Do you see why?)
The Solution
public class MostDivisors {
/* This program finds the integer between 1 and 10000 that has
the largest number of divisors. It prints out the maximum
number of divisors and an integer that has that many divisors.
*/
public static void main(String[] args) {
int N; // One of the integers whose divisors we have to count.
int maxDivisors; // Maximum number of divisors seen so far.
int numWithMax; // A value of N that had the given number of divisors.
maxDivisors = 1; // Start with the fact that 1 has 1 divisor.
numWithMax = 1;
/* Process all the remaining values of N from 2 to 10000, and
update the values of maxDivisors and numWithMax whenever we
find a value of N that has more divisors than the current value
of maxDivisors.
*/
for ( N = 2; N <= 10000; N++ ) {
int D; // A number to be tested to see if its a divisor of N.
int divisorCount; // Number of divisors of N.
divisorCount = 0;
for ( D = 1; D <= N; D++ ) { // Count the divisors of N.
if ( N % D == 0 )
divisorCount++;
}
if (divisorCount > maxDivisors) {
maxDivisors = divisorCount;
numWithMax = N;
}
}
System.out.println("Among integers between 1 and 10000,");
System.out.println("The maximum number of divisors is " + maxDivisors);
System.out.println("A number with " + maxDivisors + " divisors is " + numWithMax);
} // end main()
}
[ Exercises
| Chapter Index
| Main Index
]
