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

《欧几里得算法---求最大公因子(C++).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、欧几里得算法辗转相除法gcd(a,b)=gcd(b,amodb)(a>b且amodb不为0)r=amodbd

2、a,d

3、b，而r=a-kb，因此d

4、r#includeusingnamespacestd;intmain(){ intm,n,r; cout<<"请输入两个正整数:"<>m>>n; do {  r=m%n;  m=n;  n=r; } while(r!=0); cout<<"两个数字的最大公因子为:"<

5、includeusingnamespacestd;intEuclid(intm,intn){ intr; do {  r=m%n;  m=n;  n=r; } while(r!=0); returnm;}intmain(){ intm,n; cin>>m>>n; cout<usingnamespacestd;intEuclid(intm,intn){ if(m%n==0)  returnn; else  return

6、Euclid(n,m%n);//注意这里是n不是m,因为这里应该替换一次!}intmain(){ intm,n; cin>>m>>n; cout<usingnamespacestd;externintEuclid(intm,intn);intmain(){ intm,n; cin>>m>>n; cout<

7、n){ return(n==0)?m:Euclid(n,m%n);}