GCD function for C

Question

Q 1. Problem 5 (evenly divisible) I tried the brute force method but it took time, so I referred few 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;
}

This is very simple but I don't understand how function "gcd" works; can somebody please help me understand the logic. (I know it returns the GCD of 2 numbers but why so many operations?)

Answer 1

To your second question: The GCD function uses Euclid's Algorithm. It computes A mod B, then swaps A and B with an XOR swap. 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;
}