[已解决]算法

严凯

#include<stdio.h>
int main()
{
        int k,count=0,i,j,m,y=1;
        for(i=1;i<=2020;i++)
        {
                for(j=1;j<=2020;j++)
                {
                        m=i<j?i:j;    将i和j里面小的一个赋值给m
                        for(k=m;k>1;k--)
                        {
                                if((i%k==0)&&(j%k==0))
                                        y=k;                       //将i和j的公约数k赋值给y
                        }
                        if(y==1)          //前面定义了y=1；如果上面的if一次都没有执行，说明i和j在1到m没有公约数，则y肯定为1，则i和j的最大公约数为1，count++
                                count++;
                }
        }
                printf("%d",count);
        return 0;
}



//我这个是求i和j的最大公约数（i和j都是1到2020的数字），如果最大公约数是1，则count++，最后输出最大公约数为1的个数，我看了一下我的算法，感觉没毛病，真的，但是结果就是错的

最佳答案

月排行榜 / 总排行榜

jitianmoshen

2020-12-9 23:09:57

1. #include<stdio.h>
   
2. #define MAX 2020
   
3. int gcd(int a, int b);
   
4. int main(void)
   
5. {
   
6.     int i, j, count = 0;
   
7.     for (i = 1; i < MAX; i++)
   
8.     {
   
9.         for (j = i + 1; j <= MAX; j++)
   
10.         {
    
11.             if (gcd (i,j) == 1)
    
12.             {
    
13.                 //printf("%d %d\n",i,j);
    
14.                 count++;
    
15.             }
    
16.         }
    
17.     }
    
18.     printf("一共有%d对最大公约数为1的数\n",count);
    
19.     return 0;
    
20. }
    
21. int gcd(int a, int b)
    
22. {
    
23.     int m, c;
    
24.     //m = a * b;     //求最小公倍数时有用
    
25.     c = a % b;
    
26.     while (c)
    
27.     {
    
28.         a = b;
    
29.         b = c;
    
30.         c = a % b;
    
31.     }
    
32.     return b;
    
33. }

复制代码

跳转到最佳答案楼层

巴巴鲁

1. #include<stdio.h>
   
2. int main()
   
3. {
   
4.         int k,count=0,i,j,m,y=1;
   
5.         for(i=1;i<=2020;i++)
   
6.         {
   
7.                 for(j=1;j<=2020;j++)
   
8.                 {
   
9.                         m=i<j?i:j;    //将i和j里面小的一个赋值给m
   
10.                         for(k=m;k>1;k--)
    
11.                         {
    
12.                                 if((i%k==0)&&(j%k==0))
    
13.                                 {
    
14.                                           y=k;                       //将i和j的公约数k赋值给y
    
15.                                           break; // 再加一个break,跳出循环
    
16.                                 }
    
17.                                       
    
18.                         }
    
19.                         if(y==1)          //前面定义了y=1；如果上面的if一次都没有执行，说明i和j在1到m没有公约数，则y肯定为1，则i和j的最大公约数为1，count++
    
20.                             count++;
    
21.                 }
    
22.         }
    
23.                 printf("%d",count);
    
24.         return 0;
    
25. }

复制代码

严凯

巴巴鲁 发表于 2020-12-9 21:28

不行，还是一样的答案

jitianmoshen

1. #include<stdio.h>
   
2. #define MAX 2020
   
3. int gcd(int a, int b);
   
4. int main(void)
   
5. {
   
6.     int i, j, count = 0;
   
7.     for (i = 1; i < MAX; i++)
   
8.     {
   
9.         for (j = i + 1; j <= MAX; j++)
   
10.         {
    
11.             if (gcd (i,j) == 1)
    
12.             {
    
13.                 //printf("%d %d\n",i,j);
    
14.                 count++;
    
15.             }
    
16.         }
    
17.     }
    
18.     printf("一共有%d对最大公约数为1的数\n",count);
    
19.     return 0;
    
20. }
    
21. int gcd(int a, int b)
    
22. {
    
23.     int m, c;
    
24.     //m = a * b;     //求最小公倍数时有用
    
25.     c = a % b;
    
26.     while (c)
    
27.     {
    
28.         a = b;
    
29.         b = c;
    
30.         c = a % b;
    
31.     }
    
32.     return b;
    
33. }

复制代码

jitianmoshen

你的算法，i == 2, j == 3 和 i==3 , j == 2这种情况是不是都重复算了，你的这个算法很慢，上面那个快

1. #include<stdio.h>
   
2. int main()
   
3. {
   
4.     int k, count = 0, i, j,m;
   
5.     for(i = 1;i < 2020; i++)
   
6.     {
   
7.         for(j = i + 1;j <= 2020; j++)
   
8.         {
   
9.             //m=i<j?i:j;                 //这句没用， 2和3，3和2是一对啊
   
10.             for( k = i;k >= 1;k--)
    
11.             {
    
12.                 if((i % k == 0)&&(j % k == 0))
    
13.                     break;
    
14.             }
    
15.             if(k == 1)
    
16.                 count++;
    
17.         }
    
18.     }
    
19.     printf("%d",count);
    
20.     return 0;
    
21. }

复制代码

严凯

jitianmoshen 发表于 2020-12-9 23:16
你的算法，i == 2, j == 3 和 i==3 , j == 2这种情况是不是都重复算了，你的这个算法很慢，上面那个快

我这个就是这样的，实际上哪个i和j分别是分子和分母。对了，最小公倍数是不是最大公约数？

严凯

jitianmoshen 发表于 2020-12-9 23:09

我改了一下，我把for语句里面的j=i+1改成了j=1，就是我要的答案了，说实话，下面哪个求最大公约数我还没有见过，哪个你能在写一个就最小公倍数的算法吗？

jitianmoshen

1. int gcd(int a, int b)      //最大公约数
   
2. {
   
3.     int c;
   
4.     c = a % b;
   
5.     while (c)
   
6.     {
   
7.         a = b;
   
8.         b = c;
   
9.         c = a % b;
   
10.     }
    
11.     return b;
    
12. }
    
13. int lcm(int a, int b)         //最小公倍数
    
14. {
    
15.     return (a * b) / gcd(a,b);
    
16. }

复制代码

jitianmoshen

严凯 发表于 2020-12-10 08:43
我改了一下，我把for语句里面的j=i+1改成了j=1，就是我要的答案了，说实话，下面哪个求最大公约数我还没 ...

看楼上