GCD function for C

Question

Q 1. Problem 5 (evenly divisible) I tried the brute force method, but it took a while, so I mentioned several sites and found this code:

#include<stdio.h> int gcd(int a, int b) { while (b != 0) { a %= b; a ^= b; b ^= a; a ^= b; } return a; } int lcm(int a, int b) { return a / gcd(a, b) * b; } int main() { int res = 1; int i; for (i = 2; i <= 20; i++) { res = lcm(res, i); } printf("%d\n", res); return 0; } 

It is very simple, but I do not understand how the gcd function works; can someone please help me understand the logic. (I know that it returns a GCD of two numbers, but why are there so many operations?)

Answer 1

To your second question: the GCD function uses the Euclidean algorithm . It computes A mod B , then swaps A and B with an XOR replacement. A more readable version might look like this:

 int gcd(int a, int b) { int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } 

Answer 2

This problem can also be solved in a very clean way with recursion:

 int gcd(int a, int b) { int remainder = a % b; if (remainder == 0) { return b; } return gcd(b, remainder); } 

Answer 3

I followed these instructions for the GCD:

 #include<stdio.h> #include<conio.h> int main(){ int l, s,r; printf("\n\tEnter value : "); scanf("%d %d",&l,&s); while(l%s!=0){ r=l%s; l=s; s=r; } printf("\n\tGCD = %d",s); getch(); }