index | submit | rank | book

gcd – Greatest Common Divisor (GCD)

Write a program that computes the greatest common divisor (GCD) of two integers.

Here are a few examples:

Venn diagram for the GCD between 12 and 18

Your program should work iteratively through several pairs.

Input and Output

Input will contain multiple lines each with two integers m and n in the range 0 ≤ m, n < 1 000 000.

For each line of input your program should produce a line of output with the GCD of m and n.

Numbers given in the input may contain leading zeroes. Input is terminated by the end-of-file (EOF).

Example input

12 18
100 60
8 10

Example output


The gcd function

Your program should be implemented using an gcd function that receives two integers as arguments and returns an integer. Please refer to the information for the chosen language:

For the purposes of this exercise, you should refrain from usign the GCD function provided by your programming language if there is one. After all, the point of this exercise is to implement the GCD.


Submit your solution to be graded according to the following list:


Here are some hints:

  1. Automated judge: Keep in mind that when your program is submitted it will not be run by a human but instead by an automated judge. Instructions should be followed exactly or the judge will not give you a full score.

    Your program should not print messages like Please type two numbers: or The result is:. Instead, just print the result followed by a line break as in the example output.

  2. Produce output as you go: You do not need to accumulate input and then produce everything at the end. It is enough to produce output as you go. As soon as you read a pair of numbers write the corresponding result to the screen.

    Your program should be able to replicate the following example iterative session. Lines with two numbers are typed by the user. Lines with one number are returned by the program.

     $ ./gcd
     12 18
     100 60
     8 10
  3. Detecting the end of file. In this exercise, input is terminated by the end-of-file (EOF). Here are ways to detect EOF in C, Python and Haskell:

    • In C. The scanf function returns the numbers of items read from stdin. Since this exercise requires you to read two numbers each line, you can compare scanf’s result to one as a while condition:

        while (scanf(...)==2) {

      Which translates to, “while you’re able to read two items from standard input, do …”

    • In Python. The pattern for line in sys.stdin: can be used to create a loop where a file is processed line by line until the end-of-file (EOF).

    • In Haskell. You can use interact to declare the main function and implement your solution as a function from String to String:

        io :: String -> String
        io = ...
        main :: IO
        main = interact io

      EOF is then represented as the nil list constructor ("" or []) at the end of the argument String.

    On the terminal, you can simulate the end-of-file (EOF) by holding “Ctrl” and pressing “D”, i.e., Ctrl-D.

  4. Beware of leading zeroes. C users should beware of leading zeroes. Use %d instead of %i to avoid treating numbers with leading zeroes as octals.

try first: mult

try next: lcm

index | submit | rank | book

Copyright © 2020-2023 Rudy Matela
All rights reserved