2021 公约数

题目描述

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

如果一个整数 g 能同时整除整数 A和 B，则称 g 是 A 和 B 的公约数。例如：43 是 86 和 2021 的公约数。

请问在 1（含） 到2021（含） 中，有多少个数与 2021 存在大于 1 的公约数。请注意 2021 和 2021 有大于 1 的公约数，因此在计算的时候要算一个。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

解题思路：

提到求公约数，那么不可避免就可以想到辗转相除法！

所以，在对数据进行简单读取之后，就可以利用辗转相除法，很快的得到最大公约数，完成题目要求。

代码实现：

#include <iostream>
using namespace std;
int Gud(int a,int b)//重要,求最大公约数,最快的算法：辗转相除法
{
  int r;
  r=a%b;
  while(r!=0)
  {
      a=b;
      b=r;
      r=a%b;
  }
  return b;
}

int main()
{
  // 请在此输入您的代码
  int sum=1;//计数器
  for(int i=2;i<2021;i++)
  {
    if(Gud(i,2021)>1)
      sum++;
  }
  cout<<sum;
  return 0;
}