11

問題: 200 万以下の素数の合計を求めよ.

私はエラストテネスのふるいのことをほとんどやりました。以下のプログラムは小さな数で動作するようです。つまり、10L が答えとして 17 を生成するように LIMIT を定義します。

次のプログラムによって生成された 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;
}
4

3 に答える 3

8

素数を正しく計算しましたが、合計が大きすぎて (2^32 を超えて)、符号なし 32 ビット long に収まりません。これを修正するには、64 ビットの数値 (long long一部のコンパイラでは) を使用できます。

于 2010-01-01T14:56:25.630 に答える
1

あなたのロジックは正しいようですが、データ型とその範囲を台無しにしています。これが機能するかどうかを確認してください。

#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

于 2010-01-01T14:58:00.567 に答える
0

また、コンパイラスイッチ-std=c99も使用する必要がある場合があります。gcc（GCC）3.4.5（mingw-vista special r3）で行いました。

すなわち

gcc -Wall -std = c99 -o problem10 problem10.c

于 2010-03-30T12:23:48.033 に答える