辗转相除法

辗转相除法求最大公约数的算法：

第一步：if bnum > snum，将bnum和snum的值呼唤，使得大的数bnum为被除数；

第二步：while(bnum/snum的余数rest！=0）{

bnum=snum;

snum=rest;

}

最后，输出最大公约数rest；最小公倍数l=bnum*snum/rest;

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 int main()
 5 {
 6     int hcf(int,int);
 7     int lcf(int,int,int);
 8     int bnum,snum,h,l;
 9     printf("请输入两个数:
");
10     scanf("%d %d",&bnum,&snum);
11     printf("%d和%d的最大公约数和最小公倍数分别是:",bnum,snum);
12     h=hcf(bnum,snum);
13     printf("%d和",h);
14     l=lcf(bnum,snum,h);
15     printf("%d",l);
16     system("pause");
17     return 0;
18 }
19 int hcf(int bnum,int snum){
20     int temp,rest;
21     if(bnum<snum){
22         temp=bnum;
23         bnum=snum;
24         snum=temp;
25     }
26     while((rest=bnum%snum)!=0){//辗转相除法
27         bnum=snum;
28         snum=rest;
29     }
30     return(snum);
31 }
32 int lcf(int bnum,int snum,int h){
33     return (bnum * snum /h);
34 }