【问题描述】
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。例如，4/3，5/2，1/8，7/1都是既约分数。
请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？
答案：
2481215
分析：
开始想怎么去表示分子分母，后来想了一会儿，没必要表示出来，反正都是1–2020的数，直接判断就行了，将第一个数定位分母，第二个数定为分子，看是否二者互质（就是最大公约数为1），我们可以建立一个求最大公约数的方法，调用可以，也可以不调用直接使用也可，（第二种方法要快很多）
测试代码1：调用的方法
#include<iostream>
using namespace std;
int main()
{
int count = 0;
int gcd(int num1, int num2);
for (int i = 1; i <= 2020; i++) {
for (int j = 1; j <= 2020; j++){
int max=gcd(i, j);
if (max == 1) { count++; }
}
}
cout<< count << endl;
return 0;
}
//使用的是辗转相除法
int gcd(int num1, int num2)
{
int max = 1; //记录最大公约数
int c= num1> num2 ? num2 : num1; //c等于两数中小的数
for (int i = 1; i <= c; i++)
{
if (num1 % i == 0 && num2 % i == 0)
{
if (i > max)
max = i;
}
}
return max;
}
测试代码2：不调用，直接在主函数使用
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, m;
int temi, temj;
int sum = 0; //既约分数总数
for (int i = 1; i <= 2020; i++) //分母
{
for (int j = 1; j <= 2020; j++) //分子
{
temi = i; //暂存分子分母
temj = j;
if (temi < temj) {
n = temi;
temi = temj;
temj = n;
}
while (temi % temj != 0) //被除数在%左边，余数的在%右边
{//使用的是辗转相除法
m = temi % temj;
temi = temj;
temj = m;
}
if (temj == 1) { //temj=1说明分子分母二者最大的公约数是1
sum++;
}
}
}//输出总数
printf("%d", sum);
return 0;
}
运行结果：
