Given two integers \(a\) and \(b\), with \(a > b\). If a % b == 0, then \(b\) is the GCD of \(a\) and \(b\).

In Mathematics, GCD has the property:

$$\gcd(a,b)=\gcd(b,a\bmod b)$$

So, a "big" problem(with size \((a,b)\)) can be solved by solving a "smaller" problem(with problem size \((b,a\mod b)\)).

/*
Description: Calculate GCD of two integers a and b

Author: Liutong Xu
*/

#include<stdio.h>

int main(void)
{
    int A,B;
    int a,b;
    int temp;
    
    A = 1024;
    B = 246016;
    //scanf("%d%d",&A,&B);
    a = A;
    b = B;

    if (a < b)
    {   // 当a小于b时，交换a和b，使得a大于等于b。
        temp = a;
        a = b;
        b = temp;
    }
    
    while (a % b != 0)
    {   // 辗转相除法
        temp = a % b;
        a = b;
        b = temp;
    }
    printf("The GCD of %d and %d is %d", A, B, b);
    
    return 0;
}

stdout

The GCD of 1024 and 246016 is 256.

You have no rights to post comments