4.最大公约数-创新互联

4.大公约数

编写一个简单程序，输入两个整数，输出他们的大公约数

大公因数，也称大公约数、大公因子，指两个或多个整数共有约数中大的一个。a，b的大公约数记为（a，b），同样的，a，b，c的大公约数记为（a，b，c），多个整数的大公约数也有同样的记号。求大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。（摘自百度百科）

我们用辗转相除法来解决此问题：

以161 和 63为例简单介绍辗转相除法：

16163 = 2余35

6335 = 1余28

3528 = 1余7

287 = 4余0

大公约数为：7

当余数为0是，除数就为两个数之间的大公约数。

用C语言解决此问题，算法如下：

#includeint main() 
{ 
    int a,b;
    int c;
    scanf("%d %d",&a,&b);
    while(a%b){
        c=a%b;
        a=b;
        b=c;
    }
    c=b;
    printf("%d",c);
    return 0; 
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧