- 締切済み
中1です。500以上1000以下の素数を3つ探し、
中1です。500以上1000以下の素数を3つ探し、 それが素数であることを示してください。 それで、エラトステネスのふるいという方法を 教えてもらったのですが、 よくわからなかったので、 どなたかわかりやすく教えてください。 あと、まだルートを習っていないのでルートを使った式は わかりません・・・。 宜しくお願いします。
- みんなの回答 (2)
- 専門家の回答
関連するQ&A
- 素数を判定するいろんな方法は?
素数を判定する方法はエラトステネスのふるいの他に何かあるのでしょうか。100までは大抵の本に載っていますが、大きな数はふるいにかけても、膨大な手間がかかりそうです。
- 締切済み
- 数学・算数
- 素数をみつける方法を教えて下さい
早速ですが、素数を少しでも楽に見つけ出す方法が知りたいです。 私はエラトステネスの篩「自然数NがNの平乗根を超えない最大の整数以下の全ての素数で割り切れなければ、Nは素数である」 は知っています。他にも素数を少しでも楽に見つけ出す方法を教えてください。
- ベストアンサー
- 数学・算数
- エラトステネスのふるい(素数)についての疑問
今、家にある中学の参考書を読みながら、中学数学を勉強しているものです。その中の素数についての一番最初の問題で、 次のうちから、素数を選べ。 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で終わっている理由が分からないのです。 馬鹿みたいな問題かもしれないのですが、頭が堅くて、分からなくて困っているので、良かったら教えていただければ嬉しいです…。
- ベストアンサー
- 数学・算数
- エラトステネスのふるい java
下の問題がわかりません。どうかよろしくお願いします 問1 2以上n以下の自然数のうち、素数だけを選び出し、prime.txtという名称のファイルに書出したい。ただし、nの最大値は2^15 - 1 = 32767とする。 これをエラトステネスのふるいによって書きなさい 問2 上記の方法で作成したprime.txtを利用して、キーボードから入力する適当な自然数lを素因数分解するプログラムを作成しなさい。
- 締切済み
- Java
- 菅野正人の素数生成方法は、多項式時間計算量?
菅野が下の動画に示した素数生成メカニズムを形式化した、菅野著『数字パズル SeeK 10』などに於ける、エラトステネスの篩のアルゴリズムは、多項式時間内で素数を生成可能ですか。: https://www.youtube.com/watch?v=7u9NdEAOQaY
- ベストアンサー
- その他([技術者向] コンピューター)
- すばやく素因数分解する方法は?
「暗号解読」(サイモン・シン(著)青木薫(訳) 新潮社)という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数(合成数)を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法(素因数分解)を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法(アルゴリズム)を知りたいです。
- ベストアンサー
- 数学・算数
- C言語 エラトステネスのふるい ポインタ
C言語のプログラミングなのですがどなたか教えて頂けませんか。(説明も) エラトステネスのふるいを用いて,10000 までの自然数に素数がいくつあるかを表示するプログラムを作れ。 ただし , 配列は用いず, ポインタを用いること メモリの確保には malloを使うこと よろしくお願いいたします。
- 締切済み
- その他(インターネット・Webサービス)
お礼
ご丁寧にありがとうございます。 最後の3行が完全には理解できなかったのですが、 その他は理解できたのでよく参考になりました。 p、s これってエラトステネスとは少し違った新しい 考え方じゃないですか?? 私の勘違いかもしれないんですけど・・・