我只是个头图
已知两个数x和y，求x和y的最大公约数
暴力循环求解：
public static void gcd(int x, int y) {
if (y > x) {//如果y>x，交换x与y
int t = x;
x = y;
y = t;
}
for (int i = y; i > 0; i--) {
if (x % i == 0 && y % i == 0) {
System.out.println(i);
break;
}
}
}
辗转相除法求解：
public static void gcd(int x, int y) {
while(true) {
if(y==0) {
System.out.println(x);
break;
}
int t=y;
y=x%y;
x=t;
}
}
辗转相除法递归求解：
public static void gcd(int x, int y) {
if (y == 0) {
System.out.println(x);
return;
}
gcd(y, x % y);
}
理解辗转相除法：
理解最大公约数.png
最小公倍数：
【定理】：两个数的乘积等于这两个数的最大公约数与最小公倍数的积，即（a，b）×[a，b]=a×b，a，b的最大公约数记为（a，b），a，b的最小公倍数记为[a，b]。
所以[a，b]=a×b / (a，b)
两个数的最小公倍数求解：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int x = in.nextInt();
int y = in.nextInt();
System.out.println(lcm(x, y));
}
public static int lcm(int x, int y) {//求两个数的最小公倍数
return (x*y)/gcd(x,y);
}
public static int gcd(int x, int y) {
if (y == 0) {
return x;
}
return gcd(y, x % y);
}
}
求多个数的最大公约数和最小公倍数：
public class Main {
public static void main(String[] args) {
int[] nums = { 27, 18, 9, 81 };
System.out.println("最大公约数：" + gcdMore(nums, 3));
System.out.println("最小公倍数：" + lcmMore(nums, 3));
}
public static int gcd(int x, int y) {
if (y == 0) {
return x;
}
return gcd(y, x % y);
}
public static int lcm(int x, int y) {// 求两个数的最小公倍数
return (x * y) / gcd(x, y);
}
private static int gcdMore(int[] nums, int n) {// 求多个数的最大公约数
if (n == 1)
return nums[n - 1];
return gcd(nums[n - 1], gcdMore(nums, n - 1));
}
private static int lcmMore(int[] nums, int n) {// 求多个数的最小公倍数
if (n == 1)
return nums[n - 1];
return lcm(nums[n - 1], lcmMore(nums, n - 1));
}
}
讲解：
- 求n个数的最大公约数:采用递归。与求两个数的最大公约数一样，先将前面n-1个数的最大公约数求出来，再与第n个数进行辗转相除；
- 求n个数的最小公倍数:采用递归。与求两个数的最小公倍数一样，先将前面n-1个数的最小公倍数a求出来，再求该a与第n个数的最小公倍数；
