算法 两数互质问题,两数互质的判断方法

2021年4月22日 [题目描述]尝试一：正文来了

[题目描述]

来源于某(忘记了)题库：

请问在1 到2020 中，有多少个数与2020 互质，即有多少个数与2020 的最大公约数为1。

尝试一：

一看这道题，……

么的思路啊！

可惜：

正文来了

看了看 大佬解法(忘记大佬连接了，抱歉)，

/*** 请问在 1 到 2020 中，有多少个数与 2020 互质，即有多少个数与 2020* 的最大公约数为 1。（两个质数的判定）*/@Testpublic void test13() { int count = 0; for (int i = 1; i <= 2020; i++) { if (getMaxNum(i, 2020) == 1) { count++; //System.out.println("i = " + i); } } System.out.println("count = " + count);}/*** 这个函数是判断两个数是否为质数的函数；* 这个方法绝了……* return a % b == 0 ? b : getMaxNum(b, a % b);* 返回 1 表示互质！否则视为不互质*/public int getMaxNum(int a, int b) { if (b == 0) return a; return getMaxNum(b, a % b);}

关键在于求互质：
public int getMaxNum(int a, int b) {
if (b == 0) return a;
//return a % b == 0 ? b : getMaxNum(b, a % b);
return getMaxNum(b, a % b);
}

忘记了大佬连接，如有侵权请速联系我！抱歉！

最后，我要进大厂！加油奥里给！