エラトステネスの篩の説明

Question

実現したいこと

ソースコードのcalc関数のなかでどの行で何を行っているのかの説明

前提

c言語で書きました。
入力したn未満の素数をすべて出力するプログラム

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

#include <stdio.h>
#define MAX 1000
#define _CRT_SECURE_NO_WARNINGS

//---------------------
int input(int *n) {
	scanf_s("%d\n", n);
	return 0;
} // end of input
//---------------------
int calc(int prime_nums[], int n) {
	int i;
	int j;

	// 「エラトステネスのふるい」による処理が終了した後，prime_numsは以下のようになる．
	// prime_nums[i] = 0; iが素数でないとき
	// prime_nums[i] = 1; iが素数のとき
	
	  //?? prime_numsに適切な値を設定
	for (i = 2; i < n; i++) {
		prime_nums[i] = 1;
	}
	for (i = 2; i < n; i++) {
		if (prime_nums[i] == 1) {
			for (j = 2 * i; j < n; j++) {
				if (j%i == 0) {
					prime_nums[j] = 0;
				}
			}
		}
	}
	return 0;
} // end of calc
//---------------------
int output(int prime_nums[], int n) {
	int i;

	//?? prime_nums[i] = 1 となるiを出力する　( i<n )．
	for (i = 2; i < n; i++) {
		if (prime_nums[i] == 1) {
			printf("%d\n", i);
		}
	}
	// iを出力する書式は，”%d\n"とする．
	return 0;
} // end of output

//---------------------
int main() {
	int prime_nums[MAX];
	int n;
	int cc;

	cc = input(&n); // 求める素数の最大値を入力する nは，課題のNに相当

	cc = calc(prime_nums, n);  // 素数を求める．

	cc = output(prime_nums, n); // 求めた素数を出力する

	return 0;
} // end main

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[episteme]

しつもんはなんですか

[komkom]

calc関数のforループの中で、iの2倍をiで割った値が０になるかどうかの部分がなにをしているのかがわかりません。

[otn]

質問タイトルが「エラトステネスの篩の説明」となっていますが、エラトステネスの篩を知らない人に対して、エラトステネスの篩のやり方を日本語でも説明をしたいと言うことでしょうか？
プログラムとしては改善ポイント多数である物の、期待通り動きそうなので、
「実現したいこと」をもうすこしブレークダウンして書くと良いと思います。

[otn]

同時刻でコメントが入れ違いになってしまいました。
> iの2倍をiで割った値が０になるかどうかの部分がなにをしているのかがわかりません。
ということですが、エラトステネスの篩をどのような方法だと理解していますか？
このコードはご自分で書いた物ではないと言うことなのでしょうか？

[komkom]

返信ありがとうございます。
そうです。ほかの部分は何をしているのかはわかるのですが、素数かどうかの判別をどうやって行っているのかがわかりません。

[1T2R3M4]

>c言語で書きました。
komkomさんが書いたのですから
そのときの設計書なり、使用したアルゴリズムの資料なりを確認すれば
いいのではないでしょうか。

[otn]

18:37のコメントは、タイミング的に私の18:34のコメントへの回答かと思ったのですが、
・エラトステネスの篩をどのような方法だと理解していますか？
・このコードはご自分で書いた物ではないと言うことなのでしょうか？
について何も書かれてないのですが、18:30のコメントへの返信ですかね？
18:30のコメントは質問意図を誤解していたので無視して下さい。
（「自分ではプログラムは理解できている（＝自分で書いたのだから当然）が、コメントでどう書けばいいかについて教えて欲しい」という質問かと思っていました）

[episteme]

> 素数かどうかの判別をどうやって行っているのか

素数を選んでいるのではなく、合成数を除外しています。
つまり、pが素数なら 2p, 3p, ... np は合成数なので、それを除外します。

[episteme]

割り算(剰余)せずに素数を探すのが「エラトステネスの篩」のいいとこなんだから、
if (j%i == 0) {
prime_nums[j] = 0;
}
コレ↑やっちゃダメな気がする...

[jimbe]

言われている 25-6 行目の
>for (j = 2 * i; j < n; j++) {
>if (j%i == 0) {
は… wiki を見るだけでも違うのが分かると思います。
https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

だからこその質問かもしれませんが、それなら 1T2R3M4 さんが既に指摘されてます通り、このコードの元ネタを深堀するとか提示頂くとかが必要でしょう。

Answer 1

int calc(int prime_nums[], int n) {
  int i;
  int j;

  // 2,3,... n-1 はすべて素数(ってこと)とする。
  for (i = 2; i < n; i++) {
    prime_nums[i] = 1;
  }

  // i = 2,3,...n-1 に対し
  for (i = 2; i < n; i++) {
    // i が素数なら
    if (prime_nums[i] == 1) {
      // j = 2i, 2i+1, 2i+2, ... n-1 に対し
      for (j = 2 * i; j < n; j++) {
        // iがjを割り切る(jが素数iの倍数)ならjは素数ではない
        if (j%i == 0) {
          prime_nums[j] = 0;
        }
      }
    }
  }
  return 0;
}

ただ、これは正しい「エラトステネスの篩」の実装とは言い難い。

「エラトステネスの篩」を愚直に実装してみた:

#include <stdbool.h>

// エラトステネスの篩
// https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
void calc(bool prime_nums[], int n) {
  // step-[1]: 配列の1番目にfalseを、2番目以降に全てtrueを入れる。
  prime_nums[1] = false;
  for ( int i = 2; i < n; ++i ) {
    prime_nums[i] = true;
  }
  // step-[3]: [2]による篩い落とし操作を、
  //           走査している要素の添字がxの平方根に達するまで行う。
  for ( int i = 1; i * i < n; ++i ) {
    // step-[2].1: trueの要素を見つけたら、
    if ( prime_nums[i] ) {
      // step-[2].2: 添字pは素数である
      //             配列の p^2 以上のpの倍数番目をfalseにする。
      int p = i;
      for ( int j = p * p; j < n; j += p ) {
        prime_nums[j] = false;
      }
    }
  }
}