Amirul Umar Amirul Umar - 1 month ago 9
C Question

Ask for two integers to get greatest common divisor (GCD)?

I'm new here to this website and I hope I have a good time here. I'm currently doing an assignment and currently stuck at the first question where the program asks for two integers in order to calculate and display the greatest common divisor, or GCD.

According to the question:


The classic algorithm for computing the GCD, known as Euclid’s algorithm goes as
follows: Let m and n be variables containing the two numbers. If n is 0, then stop; m
contains the GCD. Otherwise, compute the remainder when m is divided by n. Copy n into m
and copy the remainder into n. Then repeat the process, starting with testing whether n is 0.


With that hint, I decided to write the code as follows:

#include <stdio.h>
int main() {
int first, second, m, n, GCD = 0;
printf("Enter two integers: ");
scanf("%d%d", &first, &second);
if (first > second) {
m = first;
n = second;
} else {
m = second;
n = first;
}
while(1) {
if (n == 0) {
GCD = m;
break;
} else {
m = n;
n = m % n;
}
}
printf("Greatest Common Divisor: %d\n", GCD);
}


But for some reason, GCD always prints out the smaller integer n, almost like it ignored the calculations it was supposed to make during the while loop:

Enter two integers: 12 28
Greatest Common Divisor: 12


When it should be displaying, according to sample output:

Enter two integers: 12 28
Greatest Common Divisor: 4


Is there anything I'm doing wrong?

Answer
m = n;
n = m % n;

m becomes n, then n becomes m % n which is m % m: always zero. You need to either do it simultaneously (not possible in C, as it doesn't have concurrent assignment), or use a temporary variable:

t = m;
m = n;
n = t % n;