一个既能整除 a a a 又能整除 b b b 的最大整数。

求 15 15 15 与 40 40 40 的最大公约数.

算法大致思路就是，不断地缩减 a a a 的值，直到 a < 1 a < 1 a= 1; --i) { if(a%i==0 && b%i==0) { System.out.print(i + "、"); break; //因为是最大公约数，所以要提前退出循环 --> 5 } } System.out.println(gcd(15, 40)); } } unsigned int GCD ( unsigned int M, unsigned int N) { unsigned int Rem; while(N > 0) { Rem = M % N; M = N; N = Rem; } } 求法二：递归 public static int gcd(int a, int b) { if(a == 0) return b; return gcd(b%a, a); //5 } 二、最小公倍数

公式： a 、 b a、b a、b 的最小公倍数 == a ∗ b / g c b ( a , b ) a*b / gcb(a, b) a∗b/gcb(a,b)

“约数，又称因数。整数 a a a 除以整数 b ( b ≠ 0 ) b(b≠0) b(b​=0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

例如：一个数能够整除另一数，这个数就是另一数的约数。如 2 ， 3 ， 4 ， 6 2，3，4，6 2，3，4，6 都能整除 12 12 12，因此 2 ， 3 ， 4 ， 6 2，3，4，6 2，3，4，6 都是 12 12 12 的约数。也叫因数。

两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数，叫做互质数。

根据互质数的定义，可总结出一些规律，利用这些规律能迅速判断一组数是否互质。