欧几里得算法---求最大公因子(c++).doc

欧几里得算法辗转相除法gcd(a,b)=gcd(b,amodb)(a>b且amodb不为0)r=amodbd|a,d|b,而r=a-kb,因此d|r#include<iostream>usingnamespacestd;intmain(){intm,n,r;cout<<"请输入两个正整数:"<<endl;cin>>m>>n;do{r=m%n;m=n;n=r;}while(r!=0);cout<<"两个数字的最大公因子为:"<<m<<endl;return0;},提高通用性:#include<iostream>usingnamespacestd;intEuclid(intm,intn){intr;do{r=m%n;m=n;n=r;}while(r!=0);returnm;}intmain(){intm,n;cin>>m>>n;cout<<m<<"和"<<n<<"的最大公因子为:"<<Euclid(m,n)<<endl;return0;}再试着用递归:#include<iostream>usingnamespacestd;intEuclid(intm,intn){if(m%n==0)returnn;elsereturnEuclid(n,m%n);//注意这里是n不是m,因为这里应该替换一次!}intmain(){intm,n;cin>>m>>n;cout<<m<<"和"<<n<<"的最大公因子为:"<<Euclid(m,n)<<endl;return0;}简写:#include<iostream>usingnamespacestd;externintEuclid(intm,intn);intmain(){intm,n;cin>>m>>n;cout<<m<<"和"<<n<<"的最大公因子为:"<<Euclid(m,n)<<endl;return0;}intEuclid(intm,intn){return(n==0)?m:Euclid(n,m%n);}