算法题每日一练---第19天：既约分数

一、问题描述

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

例如3/4，1/8，7/1 都是既约分数。

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

二、题目要求

考察

最大公约数、公倍数
建议用时15~25min

三、问题分析

判断一个分数是不是既约分数，要利用双重for循环分别判断分子和分母的约数，比如上面

3的公约数为1、3，4的公约数为1、2、4，两者的公约数为1，符合上述条件。

而8的约数为1 2 4 8，4的约数为1 2 4，4和8的最大公约数为4，不符合条件。

对于两个数字判断他们得到最大公约数，可以单独构造一个函数：

intgcd(intx,inty)//构造单独函数{
if(x%y==0) returny;//如果x%y没有余数，返回最大公约数yelsereturngcd(y,x%y);//重新调用计算}

举例：

假设上面的x，y分别为10、8，10%8==2，把原来的8赋值到x，取模之后的2复制到y。

现在x，y分别变成8，2，8%2==0，结束输出结果。

拓展

1.C++头文件，algorithm之中包含最大公约数__gcd(a,b)，直接使用即可

2.最小公倍数：在求出最大公约数的基础上，原来给定的两个数字相乘/最大公约数。上面给定的是10 8，最大公约数是2，所以最小公倍数：10*8/2=40。

四、编码实现

#include<iostream>usingnamespacestd;
intgcd(intx,inty)//最大公约数判断{
if(x%y==0) returny;//取模等于0，返回结果elsereturngcd(y,x%y);//重新调用计算}
intmain()
{
inti,j,n=2022;//初始化条件longlongintans=0;//ans定义为0for(i=1;i<=n;i++)//第一层for循环    {
for(j=1;j<=n;j++)//第二层for循环        {
if(gcd(i,j)==1)//判断i ,j的最大公约数是否为1            {
ans++;//判断成功，ans++            }
        }
    }
cout<<ans;//输出结果return0;
}

五、输出结果

输出结果为：2486423