[已解决]算法

严凯

#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

#include<stdio.h>
#define MAX 2020
int gcd(int a, int b);
int main(void)
{
    int i, j, count = 0;
    for (i = 1; i < MAX; i++)
    {
        for (j = i + 1; j <= MAX; j++)
        {
            if (gcd (i,j) == 1)
            {
                //printf("%d %d\n",i,j);
                count++;
            }
        }
    }
    printf("一共有%d对最大公约数为1的数\n",count);
    return 0;
}
int gcd(int a, int b)
{
    int m, c;
    //m = a * b;     //求最小公倍数时有用
    c = a % b;
    while (c)
    {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

跳转到最佳答案楼层

巴巴鲁

#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
                                          break; // 再加一个break,跳出循环 
                                }
                                      
                        }
                        if(y==1)          //前面定义了y=1；如果上面的if一次都没有执行，说明i和j在1到m没有公约数，则y肯定为1，则i和j的最大公约数为1，count++
                            count++;
                }
        }
                printf("%d",count);
        return 0;
}

严凯

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

不行，还是一样的答案

jitianmoshen

#include<stdio.h>
#define MAX 2020
int gcd(int a, int b);
int main(void)
{
    int i, j, count = 0;
    for (i = 1; i < MAX; i++)
    {
        for (j = i + 1; j <= MAX; j++)
        {
            if (gcd (i,j) == 1)
            {
                //printf("%d %d\n",i,j);
                count++;
            }
        }
    }
    printf("一共有%d对最大公约数为1的数\n",count);
    return 0;
}
int gcd(int a, int b)
{
    int m, c;
    //m = a * b;     //求最小公倍数时有用
    c = a % b;
    while (c)
    {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

jitianmoshen

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

#include<stdio.h>
int main()
{
    int k, count = 0, i, j,m;
    for(i = 1;i < 2020; i++)
    {
        for(j = i + 1;j <= 2020; j++)
        {
            //m=i<j?i:j;                 //这句没用， 2和3，3和2是一对啊
            for( k = i;k >= 1;k--)
            {
                if((i % k == 0)&&(j % k == 0))
                    break; 
            }
            if(k == 1) 
                count++;
        }
    }
    printf("%d",count);
    return 0;
}

严凯

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

int gcd(int a, int b)      //最大公约数
{
    int c;
    c = a % b;
    while (c)
    {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}
int lcm(int a, int b)         //最小公倍数
{
    return (a * b) / gcd(a,b);
}

jitianmoshen

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

看楼上