プロジェクト オイラー #10 が失敗するのはなぜですか?
-
22-09-2019 - |
質問
質問は次のとおりです。200 万以下のすべての素数の合計を求めます。
私はエラストテネスのふるいをほぼ実行しましたが、以下のプログラムは少数の場合に機能するようです。LIMIT を 10L として定義すると、答えとして 17 が生成されます。
次のプログラムで生成された 1179908154 を回答として送信しましたが、正しくありませんでした。
問題の指摘にご協力ください。ありがとう。
#include <stdio.h>
#define LIMIT 2000000L
int i[LIMIT];
int main()
{
unsigned long int n = 0, k, sum = 0L;
for(n = 0; n < LIMIT; n++)
i[n] = 1;
i[0] = 0;
i[1] = 0;
unsigned long int p = 2L;
while (p*p < LIMIT)
{
k = 2L;
while (p*k < LIMIT)
{
i[p*k] = 0;
k++;
}
p++;
}
for(n = 0; n < LIMIT; n++)
if (i[n] == 1)
{
sum += n;
}
printf("%lu\n",sum);
return 0;
}
解決
あなたは正しく素数を計算するが、合計は(32 ^ 2以上)が大きすぎると長い符号なし32ビットに収まらないだろう。あなたはこの問題を解決するために、64ビットの番号(いくつかのコンパイラでlong long
)を使用することができます。
他のヒント
あなたのロジックが正しいように思えるが、あなたはデータ型でめちゃくちゃにし、そのranges.Checkこの作品かどうかをされます:
#include <stdio.h>
#define LIMIT 2000000
int i[LIMIT];
int main()
{
long long int n = 0, k, sum = 0;
for(n = 0; n < LIMIT; n++)
i[n] = 1;
i[0] = 0;
i[1] = 0;
long long int p = 2;
while (p*p < LIMIT)
{
k = 2;
while (p*k <LIMIT)
{
i[p*k] = 0;
k++;
}
p++;
}
for(n = 0; n < LIMIT; n++)
if (i[n] == 1)
{
sum += n;
}
printf("%lld\n",sum);
return 0;
}
Output :142913828922
コンパイラ スイッチを使用する必要がある場合もあります。 -std=c99 同じように。とやった gcc (GCC) 3.4.5 (mingw-vista スペシャル r3).
つまり
GCC -WALL -STD = C99 -O問題10問題10.C
所属していません StackOverflow