gcd.c

/*
 * GCD -- compute the greatest common divisor of two integers recursively
 *
 * Usage: gcd
 *
 * Inputs: Integers m, n
 * Outputs: gcd(m, n) = g	-- m, n as above; g is gcd(m, n)
 * Errors:	- m, n not an integer
 *
 * Assumptions:	- the arguments are not digits followed by non-digits
 * 		  (unchecked)
 * 		- at least 1 of m, n is non-zero (checked)
 *
 * Matt Bishop, ECS 36A
 * October 17, 2019 -- wrote original version
 */
#include <stdio.h>

/*
 * GCD -- compute the GCD of m and n recursively
 * Parameters: m, n	2 integers of which at least 1 is non-zero
 * Returns: gcd of m and n
 * Assumptions: - at least 1 of m, n is non-zero (not checked)
 * 		- neither m, n are negative (not checked)
 * Algorithm: Euclid's Algorithm, using the relation:
 *	gcd(m, n) = gcd(n, n - m)
 * 
 */
int gcd(int m, int n)
{
	/* base case */
	if (n == 0) return(m);

	/* recursive case */
	return(gcd(n, m % n));
}

/*
 * main ro
 */
int main(void)
{
	int rv;			/* success of failure of read */
	int ch;			/* character to discard */
	int m, n;		/* numbers to compute the gcd of */
	int badct = 0;		/* number of bad arguments */

	/*
	 * loop through the argument list
	 */
	printf("> ");
	while((rv = scanf("%d,%d", &m, &n)) != EOF){
		if (rv != 2){
			fprintf(stderr, "Invalid input\n");
			/* discard the rest of the line */
			while((ch = getchar()) != '\n' && ch != EOF)
				;
			/* quit on EOF; loop on error */
			if (ch == EOF)
				return(badct);
			badct++;
			printf("> ");
			continue;
		}
		/*
		 * now check error conditions and other things
		 */
	 	/* if both m, n are 0, the gcd is undefined */
		if (m == 0 && n == 0){
			fprintf(stderr, "need at least 1 non-zero argument\n");
			printf("> ");
			continue;
		}
		/* handle negative numbers; gcd of negatives is same */
		/* as gcd of positives with same absolute values     */
		if (n < 0) n = -n;
		if (m < 0) m = -m;
		/*
		 * all's right with the world
		 * compute and print the GCD
		 */
		printf("gcd(%d, %d) = %d\n", m, n, gcd(m, n));
		/* reprompt */
		printf("> ");
	}

	/*
	 * return exit code of the number of failures
	 */
	return(badct);
}

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 36A, Programming & Problem Solving Version of April 2, 2024 at 12:13PM

You can get the raw source code here.