Chapter 3.4.2 – Example: Counting Divisors | Introduction to Programming Using Java

Chapter 3.4.2 – Example: Counting Divisors | Introduction to Programming Using Java

3.4.2  Example: Counting Divisors

Let’s look at a less trivial problem that can be solved with a for loop. If N and D are positive integers, we say that D is a divisor of N if the remainder when D is divided into N is zero. (Equivalently, we could say that N is an even multiple of D.) In terms of Java programming, D is a divisor of N if N % D is zero.

Let’s write a program that inputs a positive integer, N, from the user and computes how many different divisors N has. The numbers that could possibly be divisors of N are 1, 2, …, N. To compute the number of divisors of N, we can just test each possible divisor of N and count the ones that actually do divide N evenly. In pseudocode, the algorithm takes the form

This algorithm displays a common programming pattern that is used when some, but not all, of a sequence of items are to be processed. The general pattern is

The for loop in our divisor-counting algorithm can be translated into Java code as

On a modern computer, this loop can be executed very quickly. It is not impossible to run it even for the largest legal int value, 2147483647. (If you wanted to run it for even larger values, you could use variables of type long rather than int.)

However, it does take a noticeable amount of time for very large numbers. So when I implemented this algorithm, I decided to output a dot every time the computer has tested one million possible divisors. In the improved version of the program, there are two types of counting going on.

We have to count the number of divisors and we also have to count the number of possible divisors that have been tested. So the program needs two counters. When the second counter reaches 1000000, the program outputs a ’.’ and resets the counter to zero so that we can start counting the next group of one million. Reverting to pseudocode, the algorithm now looks like

Finally, we can translate the algorithm into a complete Java program:

Read More…

Introduction to Programming Using Java – David J. Eck

Chapter 2 – Names and Things | Introduction to Programming Using Java

Chapter 2.5 – Details of Expressions | Introduction to Programming Using Java

Chapter 2.5.1 – Arithmetic Operators | Introduction to Programming Using Java

Chapter 2.5.3 – Relational Operators | Introduction to Programming Using Java

Chapter 2.6.2 – Command Line Environment | Introduction to Programming Using Java

Chapter 2.6.3 – IDEs and Eclipse | Introduction to Programming Using Java

Chapter 3.1.3 – The Basic If Statement | Introduction to Programming Using Java