Exercise: Euclidean Algorithm

We are about to start a new topic, but before we go there, let me give you one more exercise.

This time we'll need to read two numbers from the standard input; since we cannot use anything other than getchar() for now–we'll learn about scanf a little bit later–I'll give you our toy function to read a number, read_int():

#include <ctype.h>
#include <stdio.h>

int read_int() {
	int result = 0, c;

	while (isdigit(c = getchar())) {
		result = result * 10 + (c - '0');
	}

	return result;
}

If you need a refresher on how it works, we introduced it here, feel free to go check that page if you forgot how getchar() works. For now, let's use this read_int() function twice to read two numbers, and let's learn how to use Euclidean algorithm to calculate the greatest common divisor of these two numbers.

Just in case you forgot, the greatest common divisor of the two given numbers is, by definition, a largest positive number that is a divisor of both of those numbers. If we take 36 and 24, for example, we can see that 1, 2, 3, 4, 6, 9, 12, 18, and 36 are all divisors of 36, while 1, 2, 3, 4, 6, 8, 12, 24 are all divisors of 24; the common divisors are 1, 2, 3, 4, 6, and 12, so 12 is the greatest common divisor, or gcd. We can write that gcd(36, 24) = 12.

There are several ways of finding GCD of two numbers. The most straightforward way would be to check it directly: we have a computer, and it can check many numbers, right? We could just check all numbers between 1 and the smallest of a and b, and find the largest one that still is a divisor of both a and b (so that a % i == 0 && b % i == 0). It will work for sure, but is very slow if both a and b are large. Instead of spending time on something that is not good, let's look at the simple and fast way to find GCD of two numbers: Euclidean algorithm.

The algorithm itself is simple:

• if b divides a (a % b == 0), then gcd(a, b) = b;
• otherwise, gcd(a, b) = gcd(b, a % b).

With 36 and 24, it will work this way:

1. 24 does not divide 36, the remainder 36 % 24 is 12, so gcd(36, 24) = gcd(24, 12).
2. 12 does indeed divide 24, the remainder 24 % 12 is 0, so `gcd(24, 12) = 12, so the original gcd(36, 24) = 12.

Let's take a longer example, and I will just write the triplets of a, b, and a % b:

1. 100, 66: the remainder is 34,
2. 66, 34: the remainder is 32,
3. 34, 32: the remainder 2
4. 32, 2: the remainder is 0, so the final answer gcd(100, 66) is 2.

Want to try writing this code? As always, some hints are given below.

#include <ctype.h>
#include <stdio.h>

/* we need our read_int function to read numbers */
int read_int() {
	int result = 0, c;

	while (isdigit(c = getchar())) {
		result = result * 10 + (c - '0');
	}

	return result;
}

int main() {
	int a, b;

	a = read_int();
	b = read_int();

	/* your code here! */
	/* make sure you printf the result */

	return 0;
}

The approach we take here will be similar to the one we used with Fibonacci sequence: we have a and b as our two variables, and we'll need an extra variable c to store a % b for comparison. After we assign c = a % b, we can make a step of the algorithm:

c = a % b;
a = b;
b = c;

Put this all in a while loop repeating these steps until b does not become zero, and you'll have it working! And if you still have questions, don't hesitate to ask me directly.