java：既约分数

标签：分数 既约 java gcd int num frac

程序设计

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的： ⒈ . 若 r 是 a ÷ b 的余数，且r不为0， 则 　　　gcd(a,b) = gcd(b,r) ⒉ . a 和其倍数之最大公因子为 a。 另一种写法是： ⒈ . 令r为a/b所得余数（0≤r 　　若 r= 0，算法结束；b 即为答案。 ⒉ . 互换：置 a←b，b←r，并返回第一步。

题目描述

如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。例如 \frac{3}{4} ,\frac{1}{8} ,\frac{7}{1}​， 都是既约分数。

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

 

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=i+1;j<=2020;j++){
            if(gcd(i,j)==1){
              count++;
            }
          }
          }
          System.out.println(count*2+1);  //存在有1/1 和 7/1之类的
    }
//辗转相除法
    public static int gcd(int number,int num){
        if(num==0){
          return number;
        }
        return gcd(num,number%num);
    }
}

 

标签：分数,既约,java,gcd,int,num,frac
From： https://www.cnblogs.com/mcpf/p/17031644.html