C++公约数

辗转相除，又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。 编辑本段辗转相除法的证明 证明：

设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq1＋r1（0≤r＜b）。若r1=0，则(a，b)＝b；若r1≠0，则再用r1除b，得b＝rq2＋r2（0≤r2＜r1）。若r2＝0，则(a，b)＝r1，若r2≠0，则继续用r2除r1，……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。 编辑本段辗转相除法的算法 算法

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的： 1. 若 r 是 a ÷ b 的余数, 则 (a,b) = (b,r)

2. a 和其倍数之最大公因子为 a。 另一种写法是：

1. a ÷ b，令r为所得余数（0≤r＜b） 若 r = 0，算法结束；b 即为答案。

2. 互换：置 a←b，b←r，并返回第一步。 其一 do循环 #include using namespace std; int main() {

int a,b,c,d,e;

cout<<\"请输入两个整数:\"<>a>>b; d=a;e=b;

do{c=a%b;a=b;b=c;}while(c!=0); cout<<\"最大公约数是:\"; cout<cout<<\"最小公倍数是:\"; cout<其二，递归

#include #include

int Gcd (int x,int y) {

int k; if(xif(x%y==0)

return abs(y); else

return Gcd (y,x%y); }

void main() {

int x,y,z,t;

cout<<\"请输入x=\"<>x;

cout<<\"请输入y=\"<>y;

z=Gcd (x,y); t=(x*y)/z;

cout<