求最大公约数.doc

求最大公约数方法一：连续整数检测#include 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(xy) z=y; else z=x; return(z); int main() int m,n; cout请输入m,n:mn; int k; k=gcd(m,n); coutgcd(m n)=; coutkendl; system(pause); return 0;方法二：欧几里得算法#include 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:mn; int k; k=gcd(m,n); coutgcd(m n)=; coutkendl; system (pause); return 0;方法三：分解质因数#include using namespace std;int gcd(int m,int n) int i=2,j=0,h=0; int a100,b100,c100; while(in) if(n%i=0) j+; aj=i; n=n/i; else i+; j+; aj=n; i=1; int u; u=j; while(i=j) i+; i=2; j=0; while(im) if(m%i=0) j+; bj=i; m=m/i; else i+; j+; bj=m; i=1; while(i=j) i+; int k=1; for(i=1;i=j;i+) for(k=1;k1) k=k*ch*ch-1; h=h-2; if(h=1) k=k*c1; return k; else return k;int main() int m,n; cout请输入m,n:mn; int f; f=gcd(m,n); coutgcd(m n)=; coutfendl; system(pause); return 0;4