Contents

Euclidean Algorithm

Euclidean Algorithm

Overview

One of the most ancient algorithms is the Euclidean Algorithm for finding the Greatest Common Divisor of two numbers. It is named after the Greek mathematician Euclid who first described it in 300BC.

The greatest common divisor (GCD) of two integers is the largest positive integer that evenly divides both numbers.

For example, the gcd(27, 9) is 9. Both numbers are divisible by 1 because \(\frac{27}{1}=27\) and \(\frac{9}{1}=9\). They are also both divisible by 3 because \(\frac{27}{3}=9\) and \(\frac{9}{3}=3\). These are both smaller than the greatest common divisor 9. Both numbers are divisible by 9 because \(\frac{27}{9}=3\) and \(\frac{9}{9}=1\).

The GCD algorithm can be described as a recursive mathematical function. We need to compute the modulo of two numbers. This is the remainder of division. Asking \(a \mod b = r\) is asking what is the remainder \(r\) of the division \(\frac{a}{b}\).

The GCD algorithm is given below.

\( \begin{align} \text{gcd}(a,b) =& \begin{cases} a & b=0 \\ \text{gcd}(b, a \mod b) & b > 0 \end{cases} \end{align} \)

To write this in a more programmatic way, we would use conditionals and recursion.

Function gcd(integer a,integer b)
    If b == 0 then
        Return a
    Return gcd(b, a mod b)
End Function

Example

What is the GCD of 36 and 81?

We are executing gcd(36,81). The inputs are a=36 and b=81. The value of b is clearly not zero. We need to compute \(36 \mod 81 = 36\). Since 36 is less than 81, it is the remainder of division.

We know that the gcd(36, 81) is also the gcd(81, 36). We now have a=81 and b=36. Again, b is not equal to 0. We compute \(81 \mod 36=9\). We still don’t have the answer, so we make another recursive call.

The answer to the original question is the same as the answer to gcd(36, 9). We have a=36 and b=9. We still haven’t reached b equal to 0. We compute \(36 \mod 9 = 0\). We have another recursive call to make.

The next recursive call is gcd(9,0). We have a=9 and b=0. This is the case where b is equal to 0. The GCD is 9. This is also the GCD of the original question gcd(36,81) is also 9.

In summary, we computed the following.

\( \begin{align} \text{gcd}(36,81) =& \text{gcd}(81,36) \\ \text{gcd}(81,36) =& \text{gcd}(36, 9) \\ \text{gcd}(36,9) =& \text{gcd}(9,0) \\ \text{gcd}(9,0) =& 9 \end{align} \)

Justification

Why does this algorithm work? It relies on the properties of the remainder and quotient.

When we divide (\(\frac{a}{b}\)) two integers \(a\) and \(b\), we get a remainder \(r\) and a quotient \(q\) based on the following formula.

\( \begin{align} a =& q*b+r \end{align} \)

Let us assume we have two positive integers \(a\) and \(b\). A GCD must exist for these two numbers. Let us assume that \(g\) is the GCD.

This means that when we divide \(a\) and \(b\) by \(g\), there will be no remainder. It divides both numbers evenly. This means when we look at the division formula we know that following.

\( \begin{align} a =& q_{1} * g + 0 \\ b =& q_{2} * g + 0 \end{align} \)

We don’t know the quotients. They could be anything, but we know the remainder is 0.

What happens when we compute \(a \mod b\)? There exists some quotient \(q_3\) and some remainder \(r_1\) for \(\frac{a}{b}\). We know the result will be the remainder of the division formula. We can solve this for the remainder.

\( \begin{align} a =& q_{3} * b+r_1 \\ a-r_1 =& q_{3} * b \\ -r_1 =& q_{3} * b-a \\ r_{1} =& a-q_{3} * b \end{align} \)

That means we can describe the \(a \mod b\) as

\( \begin{align} a \mod b =& a-q_{3} * b \end{align} \)

Let us plug our definitions of \(a\) and \(b\) in terms of the GCD \(g\) into this expression.

\( \begin{align} a-q_{3} * b =& (q_{1} * g + 0)-q_{3} * (q_{2} * g + 0) \\ =& q_{1} * g - q_{3} * q_{2} * g \\ =& g \left( q_{1} - q_{3} * q_{2} \right) \end{align} \)

If \(g\) is a common divisor of \(a\) and \(b\), then it is also a common divisor of \(a \mod b\).

Each recursive call will find a common divisor. We just need to make sure it is the greatest common divisor. This comes from the base case. When we compute \(a \mod b\) the answer will become zero when \(a\) divides \(b\) evenly. The first time this happens, we return the answer. We start with larger numbers and work down. The first answer we find is the greatest divisor.

This also explains why the algorithm always terminates. We can look at the value of \(b\). It must be true that \(a \mod b < b\). Every time we compute a remainder, the value of the second input into the function decreases. It moves towards 0. The code will terminate when it reaches \(b=0\).

Implementation in C

Our goal it to implement the GCD algorithm shown above. We will do so in C. We will ask the user for two numbers. Then we will compute their GCD.

Here is an example of the output we want.

Welcome to GCD Example
Enter First Positive Integer: 100
Enter Second Positive Integer: 75
The GCD of 100 and 75 is 25

The first thing we need to do is learn how to make a C program. We will start by ust printing the first line “Welcome to GCD Example”.

All C programs must contain a main function. When the compiler builds the program, it needs to know where to start. It always starts at the main function. The main function takes two arguments. They allow the program to read command like arguments.

  • argc is an integer. It contains the number of command line arguments. It is short for argument count.

  • argv is an array of strings. It contains the command line arguments the user typed. It is short for argument values.

We will not use either of these in this example, but they are part of the program and should be included.

The main program also needs to return a value. The return type of main is an integer. Traditionally, we return 0 for success and other values for errors. The programmer would want to provide a guide to what the error codes mean. These return values are given to the OS when the program exists and can be accessed after it has existed.

The starting point of every C program is given below.

int main(int argc, char** argv){
        return 0;
}

We can compile this code. It needs to be saved in a file. C programs should be in file names that end in .c. We put this code into the file gcd.c. We can compile it using gcc by typing gcc -o gcd gcd.c. We can then execute the code by running ./gcd. Nothing will happen! We don’t print anything. On unix based command like systems, you can see the return value by typing echo $? after execution has finished.

We need to print something. The print commands live in a library stdio.h. This is short for standard input/output. We need to include the code at the top of our file to be able to print.

#include "stdio.h"

int main(int argc, char** argv){
        return 0;
}

We can now use a new command called printf. This command allows us to print output. We wanted to print “Welcome to GCD Example”. In C, we use double quotes for strings and single quotes for single characters. The string ends with a \n character. This is a special character that means newline.

#include "stdio.h"

int main(int argc, char** argv){
        printf("Welcome to GCD Example\n");
        return 0;
}

Running this code on the command line produces output. In this example, we show the compile command and the execution command.

example % gcc -o gcd gcd.c
example % ./gcd           
Welcome to GCD Example

We wanted to get two numbers from the user. We need to read input typed in by the user. The most basic command to read input is getchar(). This command is also from stdio.h. It reads exactly one character from standard input. Standard input is the where the user types input on a command line system.

To read a single character we give the command char letter = getchar();. This reads the character and saves it in the variable letter. We can then print the character we read. The printf command can add the value of variables into print statements. We use a special placehold symbol to tell C where to put our variable value.

The command printf("You typed %c\n",letter); is a formatted print. The %c says we want a char variable printed at this point. Then letter is given as the input.

The revised code reads one character from the user.

#include "stdio.h"

int main(int argc, char** argv){
        printf("Welcome to GCD Example\n");
        printf("Type Something: ");
        char letter = getchar();
        printf("You typed %c\n",letter);
        return 0;
}

We want to read more than one character at a time. we can make a function that will read characters until a newline. For now, we will actually add some special rules. We will see how to resize things later.

Assumptions:

  • We will never need to read more than 100 characters

  • User will always end with a newline or end of file

The end of file is a special symbol that can be sent to denote the end of content. There is a special key combo for this in every system. It is more useful when working with files.

We also need another library stdlib.h which will be used to request memory.

We want to create a function to read from standard input. In C, we prototype our functions. At the top of the file, we list all the functions that we will need. Then below main we provide the implementations. This will become very important when our programs get big enough to span multiple files.

We will call our function readFromStdin(). It returns a pointer to a character. A pointer is a memory location in C. It is the place in memory where the data is located. A string of text in C is a collection of characters that are all next to each other in memory. The pointer tells us where in memory the first character is. We can find all the rest. In C, all strings end with a null terminator (the value 0). That is how we will find the end of the string.

char* readFromStdin();

int main(int argc, char** argv){

We start out function by requesting space to store the string. We request enough space to store 100 characters.

//Creates a buffer array
//Reads in characters until hitting newline or
//end of file
char* readFromStdin(){
	//Create an array buffer
	int bufferSize = 100;
	char* buffer = malloc(sizeof(char)*bufferSize);

Let’s look at this command in more detail malloc(sizeof(char)*bufferSize). The sizeof command tells us how many bytes are needed to store something. Asking sizeof(char) tells us how many bytes are needed to store 1 character. Then we multiply that number by the number of characters we want to store. This tells us the total number of bytes needed. The outermost function malloc allocated that many bytes of memory and returns the address of the first byte.

We now have a bug chunk of memory. In C, a character is exactly 1 byte. That means buffer is the first byte in a block of memory that is 100 bytes long.

We are going to put the characters into this memory block as we read them. We create an integer to track what position in the memory block we are at.

char* readFromStdin(){
	//Create an array buffer
	int bufferSize = 100;
	char* buffer = malloc(sizeof(char)*bufferSize);
	//Place characters into buffer starting at pos 0
	int position = 0;

We will read 1 character at a time into a variable named temp. If the character is the newline or the special end of file character, that is how we know to stop reading characters.

	char temp;
	temp = getchar();
	while(temp != EOF && temp != '\n'){

The != means not equals and && means “and”.

In the loop, we will put each character into the memory block. Then shift over one position.

	//Loop over characters
	char temp;
	temp = getchar();
	while(temp != EOF && temp != '\n'){
		buffer[position]=temp;
		temp = getchar();
		position++;
	}

Remember that all strings in C end in the null terminator which is zero. Once we are done reading the string, we need to put the null terminator in the last position. We then return the string we created.

	//Null Terminate the String
	buffer[position]=0;
	position++;
	//Return the string we read in
	return buffer;

The function is now complete.

//Creates a buffer array
//Reads in characters until hitting newline or
//end of file
char* readFromStdin(){
	//Create an array buffer
	int bufferSize = 100;
	char* buffer = malloc(sizeof(char)*bufferSize);
	//Place characters into buffer starting at pos 0
	int position = 0;
	//Loop over characters
	char temp;
	temp = getchar();
	while(temp != EOF && temp != '\n'){
		buffer[position]=temp;
		temp = getchar();
		position++;
	}
	//Null Terminate the String
	buffer[position]=0;
	position++;
	//Return the string we read in
	return buffer;
}

The memory we requested with malloc is not local to the function. This is critical. When the function ends, all its local variables are deleted. All the variables we created in the function like temp and bufferSize are removed from memory when the function ends. We need our malloc block of memory to stay until we are done with it.

We print out the string we read in the main program. Then we free the memory. We must explicity tell C it is time to release this memory.

int main(int argc, char** argv){
	printf("Welcome to GCD Example\n");
	printf("Type Something: ");
	char* text = readFromStdin();
	printf("You typed: %s\n",text);
	free(text);
	return 0;
}

We can test this code.

Welcome to GCD Example
Type Something: Cats like to wear hats
You typed: Cats like to wear hats

Let’s format this more like our expected input and output.

/**
	Read from stdin until hitting a newline

	@return A pointer to a character array (null terminated) with letters read
 */
char* readFromStdin();

int main(int argc, char** argv){
	//Print Welcome Message
	printf("Welcome to GCD Example\n");
	//Ask for first number
	printf("Enter First Positive Integer: ");
	char* firstInput = readFromStdin();
	printf("Enter Second Positive Integer: ");
	char* secondInput = readFromStdin();
	//Test:
	printf("a=%s\n",firstInput);
	printf("b=%s\n",secondInput);
	
	//Exit the Program
	return 0;
}

We can now read two inputs.

Welcome to GCD Example
Enter First Positive Integer: 12
Enter Second Positive Integer: 34
a=12
b=34

We have successfully read two numbers from the commandline. Well… maybe. Do we actually know that they are numbers? Maybe the user typed some words.

Welcome to GCD Example
Enter First Positive Integer: gotham
Enter Second Positive Integer: city
a=gotham
b=city

We need to check that the words only contain digits. This requires another function. We add a function to check if a string contains an integer. We return 1 or 0 and use a character (only 8 bits) to store the result.

/**
	Check if a string is a positive integer (contains only digits)
 
	@param str is the string to check
	@return 0 if false and 1 if true
 */
char isInteger(char* str);

This code will need to look at every letter in the string and see if they are digits or not. Every letter is stored in the compute’s memory as a number. The relationship between numbers and letters is given in the ASCII Table. The digits are summarized below.

Digit

ASCII Value

0

48

1

49

2

50

3

51

4

52

5

53

6

54

7

55

8

56

9

57

For our string to contain a number, every character has to be between 48 and 57. This is what we will check.

//Check if the string is an integer
//Loop over anc check each value is a digit
char isInteger(char* str){
	int pos=0;
	char c = str[pos];
	//Null Terminated String
	while(c != 0){
		//Check against ASCII Codes
		if(c < 48 || c > 57){
			return 0;
		}
		//Move to next character
		pos++;
		c = str[pos];
	}
	// No non-digits found
	return 1;
}

We start at the first character in the string. The value at pos=0. If we find a character that is equal to 0, we know we are at the end of the string. This is the null terminator. For every character we see, it’s ASCII value must be between 48 and 57. If it is not, we return 0 because the string is does not contain all digits. If we make it to the end of the loop without finding a non-digit, then the string is a number.

We further revise our main program.

int main(int argc, char** argv){
	//Print Welcome Message
	printf("Welcome to GCD Example\n");
	//Ask for first number
	printf("Enter First Positive Integer: ");
	char* firstInput = readFromStdin();
	if(!isInteger(firstInput)){
		printf("Input is not a positive integer.\n");
		return 1;
	}
	printf("Enter Second Positive Integer: ");
	char* secondInput = readFromStdin();
	if(!isInteger(secondInput)){
		printf("Input is not a positive integer.\n");
		return 1;
	}
	//Test:
	printf("a=%s\n",firstInput);
	printf("b=%s\n",secondInput);
	
	//Exit the Program
	return 0;
}

Now it exists early on non-numeric inputs.

Welcome to GCD Example
Enter First Positive Integer: gotham
Input is not a positive integer.

Numbers are accepted.

Welcome to GCD Example
Enter First Positive Integer: 12
Enter Second Positive Integer: 34
a=12
b=34

We have two strings that contain only digits. We can do math now right? Not exactly.

This code produces and error.

	int g = firstInput + secondInput;

Remember firstInput is the memory location of the first character in the string. It is not the actual value.

What about this?

	//Test:
	printf("a=%s\n",firstInput);
	printf("b=%s\n",secondInput);
	int g = firstInput[0] + secondInput[0];
	printf("c=%d\n",g);

It works but not the way we expect.

a=12
b=34
c=100

It added the ASCII value of 1 (49) with the ASCII value fo 3 (51) to get 100. Not exactly what we wanted. We need to make these distinct characters into a single number.

The number represented by a is \(1 * 10 + 2\) The number represented by b is \(3 * 10 + 4\). More generally if we have three characters \(c_0, c_1, c_2\) then we compute the number value as.

\(100 * c_0 + 10 * c_1 + c_2\)

Assume a string is a list of characters \(c_0, c_1, c_2, \cdots c_n\), we just need to compute the following formula.

\( \begin{align} \sum_{a=0}^{n} c[a] * 10^{n-a} \end{align} \)

We add another function to convert our strings to integers.

/**
	Convert String to Integer
 
	@param str is the string to Convert
	@return The numbers converted to an integer
 */
int strToInteger(char* str);

We need an integer result to store the final number we compute. We also need to know the position pos we are on. We again read each character until we find the null terminator. At each digit, we will have an ASCII code. We can subtract 48 to get the numerical value. See the table above to verify this makes sense.

To create the number we merge the digits with the following formula result = result*10 + digit. We multiply the current result by 10, shifting it left on position. Then we add the new digit. This will give us the same addition as shown above.

We return the number we compute.

//Loop over digits and convert to number
int strToInteger(char* str){
	int pos=0;//Position in str
	int result = 0;//place to store result
	//Get character
	char c = str[pos];
	//Loop over letters
	while(c!=0){
		//Use ASCII Codes
		int digit = c-48;
		//Shift all digits over by 1
		result = result*10 + digit;
		//Move to next character
		pos++;
		c = str[pos];
	}
	//Return the result we computed
	return result;
}

We are closing in on a full working solution. We can now add the numbers together in main.

int main(int argc, char** argv){
	
	//Print Welcome Message
	printf("Welcome to GCD Example\n");
	
	//Ask for first number
	printf("Enter First Positive Integer: ");
	char* firstInput = readFromStdin();
	if(!isInteger(firstInput)){
		printf("Input is not a positive integer.\n");
		return 1;
	}
	int a = strToInteger(firstInput);
	//Delete string it is no longer needed
	free(firstInput);
	
	//Ask for Second Number
	printf("Enter Second Positive Integer: ");
	char* secondInput = readFromStdin();
	if(!isInteger(secondInput)){
		printf("Input is not a positive integer.\n");
		return 1;
	}
	int b = strToInteger(secondInput);
	//Delete string it is no longer needed
	free(secondInput);
	
	//Compute the GCD
	int c = a + b;
	
	//Print Results
	printf("The GCD of %d and %d is %d\n",a,b,c);
	
	return 0;
}

The addition now works.

Welcome to GCD Example
Enter First Positive Integer: 12
Enter Second Positive Integer: 34
The GCD of 12 and 34 is 46

We just need to add the gcd function itself.

The gcd template is the same as it was in the previous section.

/**
	Compute the GCD using Euclid's Algorithm
 
	@param a is the first number to use
	@param b is the second number to use
	@return The GCD of a and b
 */
int gcd(int a,int b);

The implementation is based on our Psuedocode.

Function gcd(integer a,integer b)
    If b == 0 then
        Return a
    Return gcd(b, a mod b)
End Function

Is translated to the following C code.

//Implement Euclid's Algorithm
int gcd(int a,int b){
	if(b==0){
		return a;
	}
	return gcd(b,a % b);
}

We just add the function to our main program.

	//Compute the GCD
	int c = gcd(a,b);

Now, we have a fully functional example. We translated our algorithm into a fully functional program.

Welcome to GCD Example
Enter First Positive Integer: 100
Enter Second Positive Integer: 75
The GCD of 100 and 75 is 25

The complete source code is provided in the next section. It is also provided in a variety of other program languages. You should see many conceptual similarities. The specific commands and syntax are very different, but the ideas are all the same.

Complete Implementations

This algorithm can be implemented in any other programming language. Compare and contrast each of these implemenations to the one we worked through in detail.

These implementations are full working files. You can run them all. They all work the same way. The output will always look the same.

Welcome to GCD Example
Enter First Positive Integer: 100
Enter Second Positive Integer: 75
The GCD of 100 and 75 is 25

C

C is a compiled language. It is a very minimal language. Save this code in the file gcd.c. You need to compile it using gcc -o gcd gcd.c. To execute it, we would call ./gcd.

/**
  @file
  @author Mark Boady <mwb33@drexel.edu>
  @date July 11, 2022
  @section DESCRIPTION
 
  Example Program Computing the GCD
 
 */

#include "stdlib.h"
#include "stdio.h"

/**
	Read from stdin until hitting a newline

	@return A pointer to a character array (null terminated) with letters read
 */
char* readFromStdin();

/**
	Check if a string is a positive integer (contains only digits)
 
	@param str is the string to check
	@return 0 if false and 1 if true
 */
char isInteger(char* str);

/**
	Convert String to Integer
 
	@param str is the string to Convert
	@return The numbers converted to an integer
 */
int strToInteger(char* str);

/**
	Compute the GCD using Euclid's Algorithm
 
	@param a is the first number to use
	@param b is the second number to use
	@return The GCD of a and b
 */
int gcd(int a,int b);

/**
	Main Program to Compute GCD
 
 @param argc is the number of Command Line Arguments
 @param argv contains the Command Line Arguments given
 @return 0 if successful and 1 on error
 
 */
int main(int argc, char** argv){
	
	//Print Welcome Message
	printf("Welcome to GCD Example\n");
	
	//Ask for first number
	printf("Enter First Positive Integer: ");
	char* firstInput = readFromStdin();
	if(!isInteger(firstInput)){
		printf("Input is not a positive integer.\n");
		return 1;
	}
	int a = strToInteger(firstInput);
	//Delete string it is no longer needed
	free(firstInput);
	
	//Ask for Second Number
	printf("Enter Second Positive Integer: ");
	char* secondInput = readFromStdin();
	if(!isInteger(secondInput)){
		printf("Input is not a positive integer.\n");
		return 1;
	}
	int b = strToInteger(secondInput);
	//Delete string it is no longer needed
	free(secondInput);
	
	//Compute the GCD
	int c = gcd(a,b);
	
	//Print Results
	printf("The GCD of %d and %d is %d\n",a,b,c);
	
	return 0;
}


//Creates a buffer array
//Reads in characters until hitting newline or
//end of file
char* readFromStdin(){
	//Create an array buffer
	int bufferSize = 100;
	char* buffer = malloc(sizeof(char)*bufferSize);
	//Place characters into buffer starting at pos 0
	int position = 0;
	//Loop over characters
	char temp;
	temp = getchar();
	while(temp != EOF && temp != '\n'){
		buffer[position]=temp;
		temp = getchar();
		position++;
	}
	//Null Terminate the String
	buffer[position]=0;
	position++;
	//Return the string we read in
	return buffer;
}

//Check if the string is an integer
//Loop over anc check each value is a digit
char isInteger(char* str){
	int pos=0;
	char c = str[pos];
	//Null Terminated String
	while(c != 0){
		//Check against ASCII Codes
		if(c < 48 || c > 57){
			return 0;
		}
		//Move to next character
		pos++;
		c = str[pos];
	}
	// No non-digits found
	return 1;
}

//Loop over digits and convert to number
int strToInteger(char* str){
	int pos=0;//Position in str
	int result = 0;//place to store result
	//Get character
	char c = str[pos];
	//Loop over letters
	while(c!=0){
		//Use ASCII Codes
		int digit = c-48;
		//Shift all digits over by 1
		result = result*10 + digit;
		//Move to next character
		pos++;
		c = str[pos];
	}
	//Return the result we computed
	return result;
}

//Implement Euclid's Algorithm
int gcd(int a,int b){
	if(b==0){
		return a;
	}
	return gcd(b,a % b);
}

Go

Go is a compiled language. This code needs to be in a file named gcd.go. To compile the code, we tell go to build it. The command is go build gcd.go. This makes an executable gcd. We can execute the executable by typing ./gcd on the command line.

package main

/*
   Author: Mark Boady
   Date: 2/2/2021
   Drexel University

   Go Implementation of Euclid's Algorithm
*/

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

//Function Definitions

//The Euclidean Algorithm
//Assumes a and b are positive integers
func gcd(a int, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

//Ask for user input
//Repeat the question until we get a positive int
func askForInput(question string) int {
    //Print the question
    fmt.Print(question)
    //Read Input
    reader := bufio.NewReader(os.Stdin)
    text, err := reader.ReadString('\n')
    //Make sure read happened (fatal error)
    if err != nil {
        fmt.Println("Could not parse input.")
        return 0
    }
    //Remove trailing newline
    text = strings.TrimSuffix(text, "\n")
    //Convert to Integer
    userInput, err := strconv.Atoi(text)
    if err != nil {
        fmt.Println("Only Positive Integers allowed.")
        return askForInput(question)
    }
    //Make sure positive
    if userInput < 0 {
        fmt.Println("Negative Numbers not allowed.")
        return askForInput(question)
    }
    //It worked!
    return userInput
}

//Main Function of the program
func main() {
    fmt.Println("Welcome to GCD Example")
    var a int = askForInput("Enter First Positive Integer: ")
    var b int = askForInput("Enter Second Positive Integer: ")
    var result int = gcd(a, b)
    fmt.Printf("The GCD of %d and %d is %d\n", a, b, result)
    return
}

Python

Python is an interpreted language. If we save this code in a file called gcd.py then we just need to call the interpreter. On the command line, we would just have to say python3 gcd.py.

#Author: Mark Boady
#Date: 2/2/2021
#Drexel University

#Python Implementation of Euclid's Algorithm for GCD
#Assumes int(a) >= 0 and int(b) >= 0

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b, a%b)

#Ask for an int that is greater than equal to 0
def askForInput(question):
    try:
        x=input(question)
        x=int(x)
        if x >= 0:
            return x
        print("Negative Numbers not allowed.")
        return askForInput(question)
    except ValueError:
        print("Only Positive Integers allowed.")
        return askForInput(question)

#Manage the primary input/output
def main():
    print("Welcome to GCD Example")
    a=askForInput("Enter First Positive Integer: ")
    b=askForInput("Enter Second Positive Integer: ")
    result=gcd(a,b)
    outputText="The GCD of {:d} and {:d} is {:d}"
    print(outputText.format(a,b,result));

#Python executes this code when
#run directly.
if __name__=="__main__":
    main()

C++

C++ is a compiled language. Assume this code is in the file gcd.cpp. First, we need to compile it. Which compiler used will effect this command. Using the GNU C++ compiler, it would be g++ -o gcdApp gcd.cpp. We then get an executable file gcdApp. We can run this file from the command line by typing ./gcdApp.

/*
    Author: Mark Boady
    Date: 2/2/2021
    Drexel University
    
    C++ Implementation of Euclid's Algorithm
 */
 #include <iostream>
 #include <string>
 #include<limits>
 
 //Function Templates
 
 //Assumes a and b are positive integers
 int gcd(int a, int b);
 
 //Function for asking for input
 int askForInput(std::string question);
 
 //Main Function of the program
 int main(){
    std::cout << "Welcome to GCD Example" << std::endl;
    int a = askForInput("Enter First Positive Integer: ");
    int b = askForInput("Enter Second Positive Integer: ");
    int result=gcd(a,b);
    std::cout << "The GCD of " << a << " and " << b;
    std::cout << " is " << result << std::endl;
    return 0;
 }

//Functions are defined below main

//The Euclidean Algorithm
int gcd(int a, int b)
{
    if(b==0)
    {
        return a;
    }else{
        return gcd(b, a%b);
    }
}

//Ask for user input
//Repeat the question until we get a positive int
int askForInput(std::string question)
{
    //Print the question
    std::cout << question;
    int userInput;
    std::cin >> userInput;
    //See if we succeeded
    if(std::cin.fail())
    {
        //Clear the stream for the next input
        std::cin.clear();
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n');
        //Print Error
        std::cout << "Only Positive Integers allowed." << std::endl;
        //Ask Again
        return askForInput(question);
    }
    //Negative Number Error
    if(userInput < 0)
    {
        //Print Error
        std::cout << "Negative Numbers not allowed." << std::endl;
        //Ask Again
        return askForInput(question);
    }
    //It worked!
    return userInput;
}

Java

Java is a compiled language that runs in a virtual machine. Save this code in the file gcd.java. You need to compile it to Java Virtual Machine code using javac gcd.java. The executable can only be run by the Java Virtual Machine. To execute it, we would call java gcd.

/*
    Author: Mark Boady
    Date: 2/2/2021
    Drexel University
    
    Java Implementation of Euclid's Algorithm
*/
 
//Useful Libraries
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class gcd
{
    //Main Function to ask for inputs
    public static void main(String argv[])
    {
        System.out.println("Welcome to GCD Example");
        int a = askForInput("Enter First Positive Integer: ");
        int b = askForInput("Enter Second Positive Integer: ");
        int result=gcd(a,b);
        String output=String.format(
            "The GCD of %d and %d is %d"
            ,a,b,result);
        System.out.println(output);
        return;
    }
    
    //Use Euclid's algorithm to find the gcd
    public static int gcd(int a, int b)
    {
        if(b==0)
        {
            return a;
        }else
        {
            return gcd(b, a%b);
        }
    }
    
    //Function to get a positive integer
    //with input checking
    public static int askForInput(String question)
    {
        BufferedReader reader =
        new BufferedReader(new InputStreamReader(System.in));
        System.out.print(question);
        String text;
        //Java Streams can become unreadable
        try{
            text = reader.readLine();
        }catch(IOException e)
        {
            System.out.println("Could not read input.");
            return 0;//Unrecoverable
        }
        //See if it is an int
        try{
            int x = Integer.parseInt(text);
            //Make sure it is positive
            if(x >= 0)
            {
                return x;
            }
            System.out.println("Negative Numbers not allowed.");
            return askForInput(question);
        }catch(NumberFormatException e) {
            System.out.println("Only Positive Integers allowed.");
            return askForInput(question);
        }
    }
 
}

previous

Algorithms and Programs

next

Iterative Algorithms