设计出3个版本的求最大公约数的算法

#include<stdio.h> #include <iostream> using namespace std; #include<sys/timeb.h> int method1(int m,int n) { int l; if(m<n) l=m; else l=n; while(l>0) { if(m%l==0) { if(n%l==0) break; } l=l-1; } return l; } int method2(int m,int n) { int r; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } int method3(int m,int n) { int i,f=1; for(i=2;i<=m && i<=n;i++) { while(m%i==0 && n%i==0) { f*=i; m/=i; n/=i; } } return f; } int main() { int m,n,max; //cout<<"输入测试组数："; cout<<"请输入两个数m、n（空号相隔）："; while(cin>>m>>n ) { timeb t1,t2; int t; ftime(&t1); // 求得当前时间 max=method1(m,n); ftime(&t2); // 求得当前时间 t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm); // 计算时间差 cout<<m<<" "<<n<<"的最大公约数是："<<max<<", 该算法用时"<<t<<"毫秒"<<endl; ftime(&t1); max=method2(m,n); ftime(&t2); t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm); cout<<m<<" "<<n<<"的最大公约数是："<<max<<", 该算法用时"<<t<<"毫秒"<<endl; ftime(&t1); max=method3(m,n); ftime(&t2); t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm); cout<<m<<" "<<n<<"的最大公约数是："<<max<<", 该算法用时"<<t<<"毫秒"<<endl; } return 1; }