求最大公约数.doc

求最大公约数
方法一：连续整数检测
#include <iostream>
using namespace std;
int gcd(int m,int n)
{
int t;
int min(int x,int y);
t=min(m,n);
while(t)
{
if(m%t==0&&n%t==0)
break;
else
t=t-1;

}
return t;
}
int min(int x,int y)
{
int z;
if(x>y)
z=y;
else
z=x;
return(z);
}
int main()
{
int m,n;
cout<<"请输入m,n:"<<endl;
cin>>m>>n;
int k;
k=gcd(m,n);
cout<<"gcd("<<m<<" "<<n<<")=";
cout<<k<<endl;
system("pause");
return 0;
}
方法二：
欧几里得算法
#include <iostream>
using namespace std;
int gcd(int m,int n)
{
int r;
r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
return n;
}
int main()
{
int m,n;
cout<<"请输入m,n:"<<endl;
cin>>m>>n;
int k;
k=gcd(m,n);
cout<<"gcd("<<m<<" "<<n<<")=";
cout<<k<<endl;
system ("pause");
return 0;
}
方法三：
分解质因数
#include <iostream>
using namespace std;
int gcd(int m,int n)
{
int i=2,j=0,h=0;
int a[100],b[100],c[100];
while(i<n)
{
if(n%i==0)
{
j++;
a[j]=i;
n=n/i;
}
else
i++;
}
j++;
a[j]=n;
i=1;
int u;
u=j;
while(i<=j)
{
i++;
}
i=2;
j=0;
while(i<m)
{
if(m%i==0)
{
j++;
b[j]=i;
m=m/i;
}
else
i++;
}
j++;
b[j]=m;
i=1;
while(i<=j)
{
i++;
}
int k=1;
for(i=1;i<=j;i++)
{
for(k=1;k<=u;k++)
{
if(b[i]==a[k])
{
h++;
c[h]=a[k];
a[k]=a[k+1];
break;
}
}
}
k=1;
while(h>1)
{
k=k*c[h]*c[h-1];
h=h-2;
}
if(h==1)
{
k=k*c[1];
return k;
}
else
return k;
}
int main()
{
int m,n;
cout<<"请输入m,n:"<<endl;
cin>>m>>n;
int f;
f=gcd(m,n);
cout<<"gcd("<<m<<" "<<n<<")=";
cout<<f<<endl;
system("pause");
return 0;
}
4