c - 为什么 spoj 对 Euler Totient 函数的解给出了错误的答案？

Question

我正在解决ETF SPOJ的问题。我使用埃拉托色尼筛法来计算素数，然后使用 Phi 的基本定义，但 SPOJ 给出了错误的答案。我已经在 GCC 编译器上对其进行了测试，其中提到的范围为 0 到 1000,000。但找不到错误。我知道查看别人的代码有点痛苦，但我真的很感谢任何帮助。

#include<stdio.h>
#include<string.h>
#include<math.h>
#define PRIME_COUNT 2000

int main()
{
        long unsigned int number;
        long sieveArray[PRIME_COUNT],primes[PRIME_COUNT],prime_count=0;
        int i=2,j,test_cases;
        long phi, tempNumber;

        memset(sieveArray,0,PRIME_COUNT*sizeof(long));

        while(1)
        {
                if(i>PRIME_COUNT)
                        break;
                if(sieveArray[i]==0)
                {
                        primes[prime_count++]=i;
                        for(j=i;j<PRIME_COUNT;j=j+i)
                        {
                                sieveArray[j]=1; 
                        }
                }
                i++;
        }


        scanf("%d",&test_cases);

        for(i=0;i<test_cases;i++)
        {
                scanf("%ld",&number);

                if(number!=0)
                {
                        phi=number;
                        tempNumber=number;
                        for(j=0;primes[j]*primes[j]<=tempNumber;j++)
                        {
                                if(tempNumber%primes[j]==0)
                                {
                                        phi*=(primes[j]-1);
                                        phi/=primes[j];
                                        while(tempNumber%primes[j]==0)
                                                tempNumber=tempNumber/primes[j];
                                }
                        }
                        if(tempNumber!=1)
                        {
                                phi*=(tempNumber-1);
                                phi/=tempNumber;
                        }
                }
                else 
                        phi =number;

                printf("%ld\n",phi);
        }
        return 0;
}

Answer 1

将 long 更改为 long long，或者交换

                            phi*=(tempNumber-1);
                            phi/=tempNumber;

至

                            phi/=tempNumber;
                            phi*=(tempNumber-1);

(以及所有其他类似的行)将临时值保持在数据类型的范围内。先删除，然后再相乘。要了解原因，请考虑 number 是略低于上限的质数的情况。

顺便说一句，您的 if(sieveArray[i]==0) 将尝试访问 sieveArray[PRIME_COUNT] 数组的最后一位元素，当 i==PRIME_COUNT。