エラトステネスの篩のアルゴリズムで、セグメンテーションエラーが出る

Question

エラトステネスの篩のプログラムを作成しているのですが、セグメンテーションエラーが出てしまいます。

「iが消されていない時、iの倍数を消す」箇所が間違っているのはわかるのですが（コメントアウトで実行したら問題なく動いたので）、どこが間違っているのかわかりません。教えていただけたら嬉しいです。

C言語

#include <stdio.h>

#define N 100

int main(void) {
  int i, num[N+1];
//2から100までの値を代入する。
  for (i=2; i<=N; i++) num[i] = i;
//iが消されていなければ、iの倍数を消す。
  for (i=2; i<=N; i++) {
    if (num[i] == i) {
        num[i * 2] = 0;
    }
  }
  for (i=2; i<=N; i++) {
    if (num[i] != 0) printf("%3d", num[i]);
  }

  return 0;
}

Comments

[episteme]

>「iが消されていない時、iの倍数を消す」

倍数って ２倍した数 「じゃない」よ。

[hagito]

勘違いしていました。。。ご指摘ありがとうございます。

Answer 1

    num[i * 2] = 0;

これ間違ってますよ
定義された配列の範囲外を指します

Comments

[hagito]

本当ですね。。。ありがとうございます。

Answer 2

if文を次のような for文にしないと間違いです。
for (int j = i * 2; j <= N; j += i) num[j] = 0;

もちろん修正方法は他にいくつもあります。

Comments

[hagito]

ありがとうございます。

Answer 3

どこが間違っているのかわかりません。

「どこが間違っている」と表現しがたいぐらいに、完全に間違っています。

• i<=Nでi*2にアクセスすればNははみ出す
• 2倍しかチェックしていないので、9が素数扱いになる

Comments

[hagito]

ありがとうございます。助かりました。

Answer 4

        num[i * 2] = 0;

numの添字は0から100の間ではないといけません。たとえば i が 100 のときは困りますね。

Comments

[hagito]

全くその通りですね。。。ありがとうございます。