#include<iostream> using namespace std; int main() { int n1,n2,sum=0; cout<<"n1,n2:"; cin>>n1>>n2; int min=n1>=n2?n2:n1; for(int i=min;i>=1;i--) { if(n1%i==0&&n2%i==0) { sum=i; break; } } cout<<"sum:"<<sum<<endl; system("pause"); return 0; }
这个算法应该是效率最高的!
再补充一个计算n个数的最大公约数的程序。
#include<iostream> using namespace std; int gcd(int n1,int n2) { int sum=1; int min=n1>=n2?n2:n1; for(int i=min;i>=1;i--) { if(n1%i==0&&n2%i==0) { sum=i; break; } } return sum; } int Getgcd(int s[],int n) { int sum=1; sum=gcd(s[0],s[1]); for(int j=2;j<n;j++) sum=gcd(sum,s[j]); return sum; } int main() { int n,rst; cout<<"请输入数字个数:"; cin>>n; cout<<"请输入"<<n<<"个数字:"; int *s=new int [n]; for(int i=0;i<n;i++) { cin>>*(s+i); } if(n==1) rst=s[0]; else { rst=Getgcd(s,n); } cout<<"最大公约数为:"<<rst<<endl; delete [] s; system("pause"); return 0; }