欧几里得算法求最大公约数

简介

假设两个数a和b，a为不小于b的数，记a被b除的余数为r，则a可以写成：

a = b * q + r q为整数

假设a和b的一个约数为u则a和b都能被u整除

a= s * u b= t * u 其中s和t为整数 r = a - b * q = s * u - t * u * q = (s - t * q) * u

这说明r能被u整除 进一步，可以说明b和r的最大公约数是a和b的最大公约数，故找出余数和除数的最大公约数就可以啦。

举个例子

#include <stdio.h> int main() { int a,b,r; while(scanf("%d %d",&a,&b),a,b) { r = a % b; while(r != 0) { a = b; b = r; r = a % b; } printf("%d\n",b); } return 0; }

这是求两个数的最大公约数，当a=b=0时退出程序。