首页 > 代码库 > 002:求两个整数的最大公约数和最小公倍数

002:求两个整数的最大公约数和最小公倍数

求最大公约数可采用辗转相除法,其流程如图所示。

最小公倍数就是两个整数的乘积除以其最大公约数。

 1 #include <stdio.h> 2  3 int main() 4 { 5     unsigned long a, b, c=0;       //两个整数和临时变量 6     unsigned long lcm=0, gcd=0;    //最小公倍数和最大公约数 7  8     while( 1 ) 9     {10         printf("Please input two positive integers(spacebar as separator):");11         scanf("%lu %lu", &a, &b);12         if(a <= 0 || b <= 0)13         {14             printf("Input error!\n");15             continue;16         }17         else18             break;19     }20 21     unsigned long ra=a ,rb=b;      //保存原始数据22 23     while(a % b != 0)24     {25         c = a % b;26         a = b;27         b = c;28     }29     gcd = b;30     lcm = (ra * rb)/gcd;           //使用原始数据计算lcm31     printf("Their Greatest Common Divisor is %lu.\n", gcd);32     printf("Their Least Common Multiple is %lu.\n", lcm);33     34     return 0;35 }