c - 如何纠正代码中的错误以查找 Euler's Totient。有人可以纠正我出错的部分吗？

Question

这是欧拉 Totient 的例子。输入 n 的欧拉 Totient 函数 ?(n) 是 {1, 2, 3, …, n} 中与 n 互质的数字的计数，即与 n 的 GCD(最大公约数)为 1 的数字。我对 main() 函数感到震惊。根据我的直觉，它应该计算每对 gcd 的总和，每个数字都等于 1。

当进入hcf函数时，输出会迭代无限次。如果我删除 hcf 函数只是为了检查该函数所采用的对是否正确，那么它会按正确的顺序打印它们。但是，如果我在主函数中添加 hcf() ，它将进入无限循环，而不是打印等于 1 的对的 gcd 总和。

     #include<stdio.h>
      int temp,a,b,n,sum=0,i,j, gcd;

        int hcf(a,b)
        {    for(i=1; i <= a && i <= b; i++)
             {
                 if(a%i==0 && b%i==0)
                     gcd = i;
             }
                 return gcd;
        }


        void main()
        {
           printf("Enter the value of n");
           scanf("%d",&n);
           for(i=1;i<=n;i++)
           {
               for(j=1;j<=i;j++)
               {
                   printf("%d,%d\n",j,i);
                   if(hcf(j,i)==temp)
                       {
                           sum=sum+1;
                       }

                }
                printf("%d\n",sum);
                sum=0;

           }

        }

Answer 1

根本原因分析:

问题是您在两个地方递增 i (具有全局范围):1. for 循环在 main 中。 2. hcf 中的 for 循环。结果是 main 内的 for 循环中的 j 永远不会到达 i 并且您会得到一个无限循环。

<小时/>

解决方案描述:

可能的更正是限制 hcf 内 i 的范围:

#include "stdio.h"

int temp,a,b,n,sum=0,i,j, gcd;


int hcf(int a, int b)
{
    int i;
    for (i = 1; i <= a && i <= b; i++)
    {
        if (a % i == 0 && b % i == 0)
            gcd = i;
    }
    return gcd;
}


int main()
{
    printf("Enter the value of n");
    scanf_s("%d", &n);
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            printf("%d,%d\n", j, i);
            if (hcf(j, i) == temp)
            {
                sum = sum + 1;
            }

        }
        printf("%d\n", sum);
        sum = 0;
    }

    return 0;
}