26 lines
657 B
Java
26 lines
657 B
Java
package Course_Codes;
|
||
/*
|
||
* 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
|
||
如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。
|
||
请问，有多少个既约分数，分子和分母都是1到2020之间的整数（包括1和2020）？*/
|
||
public class 既约分数 {
|
||
|
||
public static void main(String[] args) {
|
||
int count=0;
|
||
int n=2020;
|
||
for(int i=1;i<=n;i++) {
|
||
for(int j=1;j<=n;j++) {
|
||
if(Gcd(i,j)==1) {
|
||
count++;
|
||
}
|
||
}
|
||
}
|
||
System.out.print(count);
|
||
}
|
||
//辗转相除法：计算公式gcd(a,b) = gcd(b,a mod b)。
|
||
public static int Gcd(int a,int b) {
|
||
//当b为0时，a就是他的们间的最大公约数
|
||
return b==0?a:Gcd(b,a%b);
|
||
}
|
||
}
|