Create a gist now

Instantly share code, notes, and snippets.

@jonenzl /euclid.c
Last active Jun 11, 2017

Embed
What would you like to do?
Determine the greatest common divisor of two integers using Euclid's algorithm
/****************************************************************************
* euclid.c
*
* Determine the greatest common divisor of two integers using Euclid's algorithm
*
* usage: ./eculid num1 num2
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
int gcdRecursive(int a, int b);
int gcdIterative(int a, int b);
int main(int argc, char *argv[])
{
// Ensure proper usage
if (argc != 3)
{
fprintf(stderr, "Usage: ./euclid num1 num2\n");
return 1;
}
// Get integers to find the greatest common divisor
int num1 = atoi(argv[1]);
int num2 = atoi(argv[2]);
// Call the recursive function to find the greatest common divisor
int gcd = gcdRecursive(num1, num2);
// Print results
printf("Recursive function:\n");
printf("The greatest common divisor of %i and %i is %i\n\n", num1, num2, gcd);
printf("Iterative function:\n");
printf("The greatest common divisor of %i and %i is %i\n", num1, num2, gcd);
return 0;
}
// Find the greatest common divisor using recursion
int gcdRecursive(int a, int b)
{
if (b == 0)
{
return a;
}
return gcdRecursive(b, a % b);
}
// Find the greatest common divisor using iteration
int gcdIterative(int a, int b)
{
int t;
while (b != 0)
{
t = b;
b = a % b;
a = t;
}
return a;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment