求最大公约数
枚举法
public class Demo3_01 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int left = scanner.nextInt();
int right = scanner.nextInt();
int result = 1;
for (int i = 2; i <= Math.min(left, right); i++) {
if ((left % i == 0) && (right % i == 0)) {
result = i;
}
}
System.out.printf("%d和%d的最大公约数为:%d", left, right, result);
}
}
辗转相除法
1.如果b等于0,计算结束,a就是最大公约数;
2.否则,计算a除以b的余数,让a等于b,而b等于那个余数;
3.回到第一步。
public class Demo3_01 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
int r = 0;//余数
int oa = a, ob = b;//保存a和b
/**
* 1.如果b等于0,计算结束,a就是最大公约数;
* 2.否则,计算a除以b的余数,让a等于b,而b等于那个余数;
* 3.回到第一步。
*/
while (b != 0) {
r = a % b;
a = b;
b = r;
}
//此时a就是最大公约数
System.out.printf("%d和%d的最大公约数为:%d", oa, ob, a);
}
}
/*
a b r
12 18 12
18 12 6
12 6 0
6 0
*/
辗转相除递归实现
public class Demo3_01 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
int res = resGcd(a, b);
//此时a就是最大公约数
System.out.printf("%d和%d的最大公约数为:%d", a, b, res);
}
private static int resGcd(int a, int b) {
if (b == 0) return a;
return resGcd(b, a % b);
}
}
标签:scanner,int,nextInt,最大公约数,public,Scanner
From: https://www.cnblogs.com/huxiaoan1/p/17519136.html