# CMPS 12A Introduction to Programming Programming Assignment 3

\$30.00

## Description

In this assignment, you will write a Java program that prompts the user for two positive integers, then prints
out the greatest common divisor of the two numbers. Your program will check its input, and will repeatedly
prompt the user until appropriate values are entered. The main control structure used in this program will
be the loop (while, do-while, or for).
The greatest common divisor (GCD) of two positive integers is, as the name implies, the largest integer that
evenly divides both numbers. For instance, the GCD of 531 and 300 is 3. One way to see this is to list all
divisors of both numbers, determine the set of common divisors, then determine the largest element in that
set.
Divisors of 531: {1, 3, 9, 59, 177, 531}
Divisors of 300: {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300}
Common Divisors of 531 and 300: {1, 3}
It follows that the GCD of 531 and 300 is 3. Another way to find the GCD is to simply compare the prime
factorizations of the two numbers. In this case
531 3359
and
300 22355
, so clearly 3 divides
both numbers, while no number larger than 3 does. The problem with these methods is that for large
integers, it is a very time consuming and computationally intensive task to determine the prime factorization
or the full set of divisors. Around 300 BC, Euclid of Alexandria discovered a very efficient algorithm for
the determination of the GCD. This algorithm is known universally today as the Euclidean Algorithm. It
uses the operation of integer division, which takes two positive integers as input, and produces two integers
as output.
Recall that if a and b are positive integers, then the quotient q and remainder r of a upon division by b are
uniquely determined by the two conditions:
a  b  q  r
and
0  r  b
. We call a the dividend, b the
divisor, q the quotient and r the remainder. If
r  0
we say that b divides evenly into a, or simply that b
divides a. (Note that the word “divisor” is used differently here than in the preceding paragraph, in which
it meant a number which divides evenly into another. The remainder need not be zero in general.) For
instance, dividing 531 by 300 yields a quotient of 1 and remainder of 231, since
531 3001 231.
We now illustrate the Euclidean Algorithm on the two numbers 531 and 300.
 Divide the larger number by the smaller, getting a quotient and remainder:
531 3001 231
 Divide the preceding divisor by the preceding remainder:
300 2311 69
 Divide the preceding divisor by the preceding remainder:
231 693 24
 Divide the preceding divisor by the preceding remainder:
69  242 21
 Divide the preceding divisor by the preceding remainder:
24 2113
 Divide the preceding divisor by the preceding remainder:
21 37  0
The process halts when we reach a remainder of 0. The GCD is then the last non-zero remainder, which is
in this case is 3. Observe that on each iteration, we discard the dividend and quotient, and save only the
divisor and remainder for the next step, on which they become dividend and divisor respectively. Note also
that the process must eventually terminate, since on each iteration the remainder is less than the divisor