Reducing Fractions and the Euclidean Algorithm in C | Program |

Today I had to write a program for cs256 in C that would reduce a fraction. First I had to find the GCF(Greatest Common Factor) of the two numbers. This algorithm is in the while loop of the program. I didn’t actually figure out the algorithm myself because we learned it in class. This is actually the Euclidean algorithm in C. Factor a is divided by factor b and then factor a is divided by the remainder. Factor a is then divided by the remainder until the remainder is zero. Once the remainder is zero, whatever the divisor was is the GCF. I don’t fully understand the mechanics of the Euclidean algorithm, but I do find it quite cool.

// This program will ask the user to enter a fraction and then reduce the fraction to its lowest terms
#include <stdio.h> // imports the necessary library.

int main(void){
	int n, d, r, gcd, nm, dm;//numerator, denominator, remainder, greatest common factor, numerator math, denominator math
	printf("Enter a fraction in the form numerator/denominator(for example 3/4 ):  "); // prompts the user to enter a fraction
	scanf("%d/%d", &n, &d); // takes input from the user
	nm = n;// nm gets the value of n and dm gets the value of d. This is so that the original n and d variables can be called after the while loop.
	dm = d;
	printf("You entered %d/%d\n", nm, dm);// tells the user what they entered
	while(dm != 0){ // while loop will not terminate until the greatest common factor is found and stored in nm
		r = nm % dm; // finds the remainder by giving r the value of nm %(modulus) dm
		nm = dm;
		dm = r;
	gcd = nm; // gcd gets the value of nm
	n = n / gcd; // reduces the fraction numerator by dividing n by the gcd
	d = d / gcd; // reduces the fraction denominator by dividing d by the gcd

	printf("The fraction in lowest terms is %d/%d", n, d); // prints the reduced fraction
	return 0;


*Enter a fraction in the form numerator/denominator(for example 3/4 ):  12/16 (The user entered 12/16)
*You entered 12/16
*The fraction in lowest terms is 3/4