1

問題: n と n + 1 の正の約数が同じである、1 < n < 10^7 の整数の数を見つけます。たとえば、14 には正の約数 1、2、7、14 があり、15 には 1、3、5、15 があります。

C と私にとっては大きすぎるため、10^7 に到達できません。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

1 分以内に問題を解決する方法のヒントとして、2 から 10^7 までの各数値を調べ、それらの数値のすべての倍数をループし、1 ずつ増やします (すべての数値は 1 の倍数であるため、1 は無視されます)。 ）。最後に、配列内の各数値の約数を取得します (コンパイラが 32 ビット インデックスをサポートしているかどうかを確認してください)。最終的な線形スキャンを使用してカウントするだけです。

于 2012-09-30T10:58:15.797 に答える
2

試したことはありlong long num = 100000000LL;ますか？C は左側から右側の型を結論付けるほどスマートではないlong longため、. を追加する必要がありますLL。このアプローチでは、関数と変数を適切な方法で変更するだけで、通常の整数よりも大きな数を処理できるはずです。

Along longは常にウィキペディア2^64で確認できるサイズです。

ヒント:誰かがコメントで言及したように、Project Euler はブルートフォースに関するものではありません。これは不十分なアプローチです。より良い戦略を考えてみましょう。math.stackexchangeで助けを得たいと思うかもしれませんか?

編集：私はなぜ私が考えたのかわからuint32_tない10^7.

于 2012-09-30T10:34:51.053 に答える
1

nhahtdh のアイデアを拡張し、さらに高速化するために (より複雑にするという代償を払って)、sqrt(10^7) = 約 3170 までの素数を計算する素数ふるいを作成します。 (exp+1) の積がその数を割る整数の数になるようにします。したがって、配列を 1 に設定し、各素数をループして、乗算する位置ごとにその素数指数の寄与 (プラス 1) を掛けることができます。

于 2016-08-19T13:55:13.743 に答える