c语言中用辗转相除法求两个数的最大公约数,C语言辗转相除法求2个数的最小公约数... |
您所在的位置:网站首页 › c语言中用辗转相除法求最大公约数 › c语言中用辗转相除法求两个数的最大公约数,C语言辗转相除法求2个数的最小公约数... |
辗转相除法最大的用途就是用来求两个数的最大公约数。 用(a,b)来表示a和b的最大公约数。 有定理: 已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c)。 (证明过程请参考其它资料) 例:求 15750 与27216的最大公约数。 解: ∵27216=15750×1+11466 ∴(15750,27216)=(15750,11466) ∵15750=11466×1+4284 ∴(15750,11466)=(11466,4284) ∵11466=4284×2+2898 ∴(11466,4284)=(4284,2898) ∵4284=2898×1+1386 ∴(4284,2898)=(2898,1386) ∵2898=1386×2+126 ∴(2898,1386)=(1386,126) ∵1386=126×11 ∴(1386,126)=126 所以(15750,27216)=126 辗转相除法比较适合用来求两个比较大的数的最大公约数 。 代码如下: #include int main() { int a,b,temp,x; scanf("%d%d",&a,&b); if(a>b) { temp=b; b=a; a=temp; } while(b%a!=0) { x=b%a; b=a; a=x; } printf("%d",a); } 以上所述是小编给大家介绍的C语言辗转相除法求2个数的最小公约数,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持! |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |