目录

题目描述

思想：

求最大公约数

代码

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果一个分数的分子和分母的最大公约数是 11，这个分数称为既约分数。

例如 34,18,7143​,81​,17​， 都是既约分数。

请问，有多少个既约分数，分子和分母都是 11到 20202020 之间的整数（包括 11 和 20202020）？

思想：

求最大公约数-辗转相除法

（16，12）-（12，16%12=4）-（4，12%4=0）- 余数为0则得最大公约数4

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        int count = 0;
        for(int i = 1; i <= 2020; i++){
          for(int j = 1; j <= 2020; j++){
            if(gcd(i, j)==1){
              count++;
            }
          }
        }
        System.out.println(count);
    }
    public static int gcd(int a, int b){
        f(b==0){
          return a;
        }
        return gcd(b, a%b);
    }
}