質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.39%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

1回答

901閲覧

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

komkom

総合スコア2

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2023/05/21 08:49

実現したいこと

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

前提

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

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

エラーメッセージ

該当のソースコード

c

1#include <stdio.h> 2#define MAX 1000 3#define _CRT_SECURE_NO_WARNINGS 4 5//--------------------- 6int input(int *n) { 7 scanf_s("%d\n", n); 8 return 0; 9} // end of input 10//--------------------- 11int calc(int prime_nums[], int n) { 12 int i; 13 int j; 14 15 // 「エラトステネスのふるい」による処理が終了した後,prime_numsは以下のようになる. 16 // prime_nums[i] = 0; iが素数でないとき 17 // prime_nums[i] = 1; iが素数のとき 18 19 //?? prime_numsに適切な値を設定 20 for (i = 2; i < n; i++) { 21 prime_nums[i] = 1; 22 } 23 for (i = 2; i < n; i++) { 24 if (prime_nums[i] == 1) { 25 for (j = 2 * i; j < n; j++) { 26 if (j%i == 0) { 27 prime_nums[j] = 0; 28 } 29 } 30 } 31 } 32 return 0; 33} // end of calc 34//--------------------- 35int output(int prime_nums[], int n) { 36 int i; 37 38 //?? prime_nums[i] = 1 となるiを出力する ( i<n ). 39 for (i = 2; i < n; i++) { 40 if (prime_nums[i] == 1) { 41 printf("%d\n", i); 42 } 43 } 44 // iを出力する書式は,”%d\n"とする. 45 return 0; 46} // end of output 47 48//--------------------- 49int main() { 50 int prime_nums[MAX]; 51 int n; 52 int cc; 53 54 cc = input(&n); // 求める素数の最大値を入力する nは,課題のNに相当 55 56 cc = calc(prime_nums, n); // 素数を求める. 57 58 cc = output(prime_nums, n); // 求めた素数を出力する 59 60 return 0; 61} // end main 62 63 64 65

試したこと

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

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

episteme

2023/05/21 09:25

しつもんはなんですか
komkom

2023/05/21 09:30

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

2023/05/21 09:30

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

2023/05/21 09:34

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

2023/05/21 09:37

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

2023/05/21 09:38

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

2023/05/21 09:44

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

2023/05/21 10:31

> 素数かどうかの判別をどうやって行っているのか 素数を選んでいるのではなく、合成数を除外しています。 つまり、pが素数なら 2p, 3p, ... np は合成数なので、それを除外します。
episteme

2023/05/21 10:53

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

2023/05/21 16:53 編集

言われている 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 さんが既に指摘されてます通り、このコードの元ネタを深堀するとか提示頂くとかが必要でしょう。
guest

回答1

0

ベストアンサー

C

1int calc(int prime_nums[], int n) { 2 int i; 3 int j; 4 5 // 2,3,... n-1 はすべて素数(ってこと)とする。 6 for (i = 2; i < n; i++) { 7 prime_nums[i] = 1; 8 } 9 10 // i = 2,3,...n-1 に対し 11 for (i = 2; i < n; i++) { 12 // i が素数なら 13 if (prime_nums[i] == 1) { 14 // j = 2i, 2i+1, 2i+2, ... n-1 に対し 15 for (j = 2 * i; j < n; j++) { 16 // iがjを割り切る(jが素数iの倍数)ならjは素数ではない 17 if (j%i == 0) { 18 prime_nums[j] = 0; 19 } 20 } 21 } 22 } 23 return 0; 24}

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

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

C

1#include <stdbool.h> 2 3// エラトステネスの篩 4// 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 5void calc(bool prime_nums[], int n) { 6 // step-[1]: 配列の1番目にfalseを、2番目以降に全てtrueを入れる。 7 prime_nums[1] = false; 8 for ( int i = 2; i < n; ++i ) { 9 prime_nums[i] = true; 10 } 11 // step-[3]: [2]による篩い落とし操作を、 12 // 走査している要素の添字がxの平方根に達するまで行う。 13 for ( int i = 1; i * i < n; ++i ) { 14 // step-[2].1: trueの要素を見つけたら、 15 if ( prime_nums[i] ) { 16 // step-[2].2: 添字pは素数である 17 // 配列の p^2 以上のpの倍数番目をfalseにする。 18 int p = i; 19 for ( int j = p * p; j < n; j += p ) { 20 prime_nums[j] = false; 21 } 22 } 23 } 24}

投稿2023/05/22 00:11

編集2023/05/22 00:14
episteme

総合スコア16612

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.39%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問