首页 > 代码库 > 辗转相除法
辗转相除法
辗转相除法求最大公约数的算法：
第一步：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("请输入两个数:\n");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 }
辗转相除法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。