既约分数（蓝桥杯）

既约分数

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如 3/4，1/8，7/1 ， 都是既约分数。
请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？

答案：2481215

c++[__gcd()函数]

#include 
using namespace std;
int main()
{
  int i,j,count=0;
  for(i=1;i<=2020;i++)
    for(j=1;j<=2020;j++)
      if(__gcd(i,j)==1)
        count++;
  cout<<count<<endl;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

c语言

辗转相除法

对辗转相除法不懂的可以看我这篇博客：辗转相除法求最大公约数，最小公倍数

#include
//辗转相除法 
/*
int get_jiyue(int a,int b)
{
  int t=a%b;
  while(t!=0)
  {
    a=b;
    b=t;
    t=a%b;
  }
  return b;
}
*/
int get_jiyue(int a,int b)
{
	if(b==0)
		return a;
	else
		return get_jiyue(b,a%b);
} 

int main()
{
  int i,j;
  int count=0;
  for(i=1;i<=2020;i++)
  {
    for(j=1;j<=2020;j++)
    {
      if(get_jiyue(i,j)==1)
      {
        count++;
      }
    }
  }
  printf("%d",count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

暴力破解，运算超时

#include

int get_jiyue(int a,int b)
{
  int min=a>b?a:b;
  int i;
  int count=0;
  for(i=1;i<=min;i++)
  {
    if(a%i==0&&b%i==0)//1是所有数字的因子 
    {
      count++;
    }
  }
  if(count==1)//如果count只有1个，说明1是这两个数的最大公约数 
  {
    return 1;
  }
  else 
  {
    return 2;
  }
}

int main()
{
  int i,j;
  int cishu=0;
  for(i=1;i<=2020;i++)
  {
    for(j=1;j<=2020;j++)
    {
    	
           if(get_jiyue(i,j)==1)
          {
             cishu++;
          }
        
    }
  }
  printf("%d",cishu);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42