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;
}
/*
*Output:
*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
*/