## 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

maxDivisorsto keep track of the largest number of divisors we have seen so far and usenumWithMaxto 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 thanmaxDivisors, we have to make note of that fact by changing the values ofmaxDivisorsandnumWithMax. At the end of the process,maxDivisorswill be the absolute maximum number of divisors andnumWithMaxwill be a number that had that many divisors. These are the values we want to print out. We can express this with a pseudocode algorithmfor 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 numWithMaxHowever, there is a problem here: The very first time

maxDivisorsis used in the test "If that number is greater than maxDivisors," the variablemaxDivisorshasn't yet been assigned a value. The computer will report this as an error. This can be fixed by assigning a value tomaxDivisorsbefore the beginning of theforloop. One way to do this is to handleN=1as a special case before the loop and then to letNgo from 2 to 10000 in the for loop. We know thatN=1has 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 numWithMaxHere'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 ofnumWithMax. It will say that the variablenumWithMaxmight not have been initialized. That is, it might never have been assigned a value. Now,youknow that it will be assigned a value (since whenN=2is processed,numWithMaxwill become 2). However, when the computer compiles the program,itdoesn't know whether the body of theifstatement will ever be executed, so it doesn't know whethernumWithMaxwill 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 anotherforloop, so we have here an example of oneforloop 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 numWithMaxThis 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 ]