辗转相除法（也称欧几里得算法）是一种用来求两个正整数的最大公约数的算法。
具体来说，辗转相除法的基本思路是：
确定两个正整数 a 和 b，其中 a 是大于 b 的。 计算 a 除以 b 的余数 r。 如果 r=0，则 b 就是 a 和 b 的最大公约数，算法结束。 否则，将 b 赋值给 a，将 r 赋值给 b，并回到第二步。 举个例子，如果我们要求 36 和 24 的最大公约数，可以按照如下步骤进行计算：
a=36，b=24 36 ÷ 24 = 1 … 12（12 为余数） a=24，b=12 24 ÷ 12 = 2 … 0（0 为余数） 根据辗转相除法的定义，在第三步时算法结束，因此 36 和 24 的最大公约数就是 12。
辗转相除法是一种非常有效的算法，时间复杂度为 O(log n)，在计算机科学中广泛应用。
下面通过一道例题来巩固说明
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
public class Main {
public static void main(String[] args) {
int count = 0;
for (int i = 1; i <= 2020; i++) {
for (int j = i + 1; j <= 2020; j++) {
if (gcd(j, i) == 1) {
count++;
}
}
}
//小在分子 大在分母 1/1 特殊情况
System.out.println(count * 2 + 1);
}
// a大 b小
public static int gcd(int a, int b) {
return b == 0 ? a:gcd(b, a%b);
}
}
例如 3/4,1/8,7/1都是既约分数。
请问，有多少个既约分数，分子和分母都是 11 到 20202020 之间的整数（包括 11 和 20202020）？
参考阅读
您阅读本篇文章共花了：
发表评论