1

问题：求整数个数 1 < n < 10^7，其中 n 和 n + 1 具有相同数量的正因数。例如，14 具有正因数 1、2、7、14，而 15 具有 1、3、5、15。

我无法达到 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;
}
4

3 回答 3

3

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

于 2012-09-30T10:58:15.797 回答
2

试过long long num = 100000000LL;吗？C 不够聪明，无法从左侧总结右侧的类型，long long因此您必须添加LL. 使用这种方法，您应该能够处理比普通整数更大的数字，只需以合适的方式更改您的函数和变量。

A的大小long long始终至少为2^64一点，您可以在Wikipedia上查看。

提示：正如评论中提到的那样，Project Euler 不是暴力破解。这是一种蹩脚的方法。考虑一些更好的策略。您可能想在math.stackexchange获得帮助？

编辑：我不知道为什么我认为 auint32_t还不够10^7- 对不起那个错误。

于 2012-09-30T10:34:51.053 回答
1

To expand on nhahtdh's idea, to make it even faster (at cost of making it more complicated), make a prime number sieve calculating the prime numbers up to sqrt(10^7) = about 3170. Then the exponents of prime factors determine the number of multiples so that the product of (exp+1) is the number of integers dividing the number. So you can set an array to ones, then loop over each prime, multiplying with that primes exponent contribution (plus one) for each position it multiplies.

于 2016-08-19T13:55:13.743 回答