项目Euler #179

Question

问题:求整数1

我不能达到10^7，因为它对C和我来说太大了。我如何在C中解决这个问题？

#include<stdio.h>
#include<conio.h>

int divisorcount(int);

int main()
{
    int number,divisornumber1,divisornumber2,j=0;

    for(number=1;number<=100;number++){
        divisornumber1=divisorcount(number);
        divisornumber2=divisorcount(number-1);
        if(divisornumber1==divisornumber2){
            printf("%d and %d\n",number-1,number);
            j++;
        }
    }
    printf("\nThere is %d integers.",j);

    getch();
}

int divisorcount(int num)
{
    int i,divi=0;
    for(i=1;i<=(num)/2;i++)
        if(num%i==0)
            divi++;
    return divi;
}

Answer 1

有没有试过long long num = 100000000LL;？C不够聪明，不能从左边的long long中推断出右边的类型，所以你必须添加LL。使用这种方法，你应该能够处理比普通整数更大的数字，只需以适当的方式改变你的函数和变量即可。

long long的大小至少是2^64位，你可以在Wikipedia上查看。

提示:正如有人在评论中提到的那样，Project Euler不是关于暴力的。这是一种蹩脚的方法。想一些更好的策略。您可能需要在math.stackexchange上获得帮助

编辑：我不知道为什么我会想，一个uint32_t对10^7来说是不够的--为那个错误道歉。

Answer 2

作为如何在一分钟内解决问题的提示，您可以遍历从2到10^7的每个数字，遍历这些数字的所有倍数并递增1 (1被忽略，因为所有数字都是1的倍数)。最后，您将获得数组中每个数字的除数个数(检查您的编译器是否支持32位索引)。只需使用最后的线性扫描进行计数。

Answer 3

为了扩展nhahtdh的想法，使其更快(以使其更加复杂为代价)，使用质数筛选器计算素数，直到sqrt(10^7) =约3170。然后，素数因子的指数决定了倍数的数量，因此(exp+1)的乘积是整数除以该数字的数量。因此，您可以将数组设置为1，然后循环每个质数，乘以它乘以的每个位置的质数指数贡献(加1)。