エラトステネスの篩(ふるい)について
- エラトステネスの篩(ふるい)について質問があります。
- 素数リストの最大値が11のところで残っている数を素数と考えると、17の倍数の削除が働かないことがあります。
- エラトステネスの篩(ふるい)について理解が足りない部分があり、考え方ややり方について教えていただけると幸いです。
- ベストアンサー
エラトステネスの篩(ふるい)について
素数を求めるアルゴリズム「エラトステネスの篩(ふるい)」について質問があります。 Wikipedia によると http://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 【ステップ４】 探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。 と記載されています。 2～1000の間にある素数を調べる場合は、 素数リストの最大値が11のところで累乗が1000 を超えるため 残っている数が素数ということなります。 実際試してみたところ、493 を素数と見なしてしまいました。 493 は 17の倍数なのですが、上記のとおり素数リストの最大値が11のところで 残っている数を素数と考えると、17の倍数の削除が働きません。 ほかの質問でエラトステネスの篩(ふるい)について質問されている方がおられるようですが もうひとつ理解が足りませんでしたので、申し訳ありませんが 考え方、やり方の間違いなどについて、ご教授をお願いします。
- oshiete811
- お礼率63% (7/11)
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
＞素数リストの最大値が11のところで累乗が1000 を超えるため 11の平方、つまり11の2乗は121です。 まだ1000を超えていません。 ここが間違っています。 1000をはじめて超える素数の2乗は37の2乗=1369だと思います。
関連するQ&A
- エラトステネスのふるい（素数）についての疑問
今、家にある中学の参考書を読みながら、中学数学を勉強しているものです。その中の素数についての一番最初の問題で、 次のうちから、素数を選べ。 1 6 13 25 51 79 87 91 という問題があり、その解法の一つでエラトステネスのふるいというもの（2から順に自然数を書き、2を残して2の倍数を消し、3を残して3の倍数を消し、5を残して5の倍数を消す、以下同様にして求める…という方法）があるのですが、上の問題でずっとエラトステネスのふるいを使いながら合成数を消していくと、11の倍数を消すところで、「13、79は11で割り切れず、13÷11、79÷11ともに商が11より小さくなるから素数である。」と参考書にあり、そこでふるいをかける作業は終わっています。 この参考書（特に、"13÷11、79÷11ともに商が11より小さくなるから素数である。"というところ）のこの部分と、ずっとにらめっこをしてきたのですが、何故「13÷11、79÷11ともに商が11より小さくなるから素数である」と言い切れるのか、分かりませんでした…。 少なくとも13は、次に11の倍数となる数である11×2=22の間に13が存在しないから素数、と言い切れる感じはするのですが、79だと、たとえ11で割り切れなくても、13、17で割り切れるかもしれない…（もちろん実際そんなことはないのですが）、と、感覚的にそう思ってしまいます。そして、「13÷11、79÷11ともに商が11より小さくなるから素数である」を言いかえれば、「商が11より大きくなる場合は、素数でない可能性がある（121以降の数であれば、たとえ今の時点で11で割り切れなくても、素数でないかもしれない）」というのも、よく分かりません…。 そんなこんなで、このふるいが11で終わっている理由が分からないのです。 馬鹿みたいな問題かもしれないのですが、頭が堅くて、分からなくて困っているので、良かったら教えていただければ嬉しいです…。
- ベストアンサー
- 数学・算数
- 探索・整列アルゴリズムのメリット・デメリットについ
「コンピューターはなぜ動くのか？」の第５章の「アルゴリズムと仲良くなる7つのポイント」のところにて、主な定番アルゴリズムとして、 表5.1 主な定番アルゴリズム (1)ユーグリットの互除去 (2)エラトステネスのふるい (3)線型探索 (4)2分探索 (5)ハッシュ法 (6)バブル・ソート (7)クイック・ソート 上記のアルゴリズムがあり、そのアルゴリズムの用途には (1)最大公約数のアルゴリズム (2)素数のアルゴリズム (3)データ探索のアルゴリズム (4)整列のアルゴリズム 上記のアルゴリズムがありますが、(3)～(4)のアルゴリズムの用途においてのメリット・デメリット ・データ探索のアルゴリズム (3)線型探索 (4)2分探索 (5)ハッシュ法 についてのメリット・デメリット ・整列のアルゴリズム (6)バブル・ソート (7)クイック・ソート についてのメリット・デメリット これらを教えて頂けばと思っております。 よろしくお願いたします。
- 締切済み
- その他([技術者向] コンピューター)
- 定番アルゴリズムのメリット・デメリットについて
定番アルゴリズムとして以下のアルゴリズムが挙げられますが、 (1)ユークリッドの互徐法 (2)エラトステネスのふるい (3)線型探索 (4)二分探索 (5)ハッシュ探索 (6)バブル・ソート (7)クイック・ソート ↑これらの各々のアルゴリズムのメリット・デメリットについてをそれぞれ教えてください。 よろしくお願いします。
- 締切済み
- その他([技術者向] コンピューター)
- ユークリッドの素数無限の証明を教えて
ユークリッドの素数無限の証明で分からないところがあります。 とりあえずWikipwdiaから引用します。 素数が無数に存在することの証明 - Wikipedia https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E3%81%8C%E7%84%A1%E6%95%B0%E3%81%AB%E5%AD%98%E5%9C%A8%E3%81%99%E3%82%8B%E3%81%93%E3%81%A8%E3%81%AE%E8%A8%BC%E6%98%8E a, b, …, k を任意に与えられた素数のリストとする。その最小公倍数 P := a × b × ⋯ × k に 1 を加えた数 P + 1 は、素数であるか、合成数かのいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。 素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能だからである。任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。 ---- 引用ここまで ---- 前半はわかります。後半の「リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能」の部分がどうもわかりません。 「リスト中の素数は P を割り切る」のは当然ですが、だとするとなぜ「P + 1 を割り切ることは不可能」になるのかつながりませんでした。 なぜ「P + 1 を割り切ることは不可能」なのでしょうか？ この点について教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- エラトステネスのふるい java
下の問題がわかりません。どうかよろしくお願いします 問1 2以上ｎ以下の自然数のうち、素数だけを選び出し、prime.txtという名称のファイルに書出したい。ただし、ｎの最大値は2^15 - 1 = 32767とする。 これをエラトステネスのふるいによって書きなさい 問2 上記の方法で作成したprime.txtを利用して、キーボードから入力する適当な自然数lを素因数分解するプログラムを作成しなさい。
- 締切済み
- Java
- 複素数の積（累乗を除く）を扱う物理の分野はありますか？
複素数の積（累乗を除く）を扱う物理の分野はありますか？ (a+bi)*(c+di) (a,b,c,d:0でない実数 かつ a≠c かつ b≠d) のような複素数の積（累乗を除く）は量子を扱わない物理の分野でありますか？ また、ありましたらその計算例を教えてください。 先程同じような質問しましたが、 複素数にも累乗があることすっかり失念していまして、 もう一度累乗を覗いて質問させていただきました。
- 締切済み
- 物理学
- 素数をみつける方法を教えて下さい
早速ですが、素数を少しでも楽に見つけ出す方法が知りたいです。 私はエラトステネスの篩「自然数NがNの平乗根を超えない最大の整数以下の全ての素数で割り切れなければ、Nは素数である」 は知っています。他にも素数を少しでも楽に見つけ出す方法を教えてください。
- ベストアンサー
- 数学・算数
- 菅野正人の素数生成方法は、多項式時間計算量？
菅野が下の動画に示した素数生成メカニズムを形式化した、菅野著『数字パズル SeeK 10』などに於ける、エラトステネスの篩のアルゴリズムは、多項式時間内で素数を生成可能ですか。： https://www.youtube.com/watch?v=7u9NdEAOQaY
- ベストアンサー
- その他([技術者向] コンピューター)
- Wikipediaの「A*」の項目の「m の親を n として記録する。
Wikipediaの「A*」の項目の「m の親を n として記録する。」という意味が分かりません Wikipediaの「A*」という探索アルゴリズムのページ（http://ja.wikipedia.org/wiki/A*）の 「アルゴリズムの流れ」という項目内なのですが、 "m が Openリストにも Closeリストにも含まれていない場合 f*(m) = f '(m) とし m を Openリストに追加する。このとき m の親を n として記録する。" とあるのですが、「mの親」とは何のことを指しているのでしょうか？ mの前のノードだとするとnと同じなのでは？と思うのですが、 それだと親という言葉をつける意味がない気がして分かりません。
- ベストアンサー
- その他（プログラミング・開発）
お礼
回答ありがとうございます。 とんでもない初歩的なミスでした。。。お恥ずかしい。 ありがとうございました。