- 締切済み
素数を判定するいろんな方法は？
素数を判定する方法はエラトステネスのふるいの他に何かあるのでしょうか。１００までは大抵の本に載っていますが、大きな数はふるいにかけても、膨大な手間がかかりそうです。
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- oyaoya65
- ベストアンサー率48% (846/1728)
以下に代表的な判定法の掲載URLを載せておきます。 これらのどれかが数式処理ソフトに組み込まれていますので私はMathematica/Mapleなどであっという間に判定できます。これも先人のおかげですね。 AKS素数判定法 http://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95 フェルマーの小定理を使う方法 http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html ミラーラビン法とルーカスレーマー法による素数判定法 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/STUDENT/KENKYU2004/okagaki.pdf http://www.th.cs.meiji.ac.jp/enc/moriya/prime.html
お礼
ありがとうございました。
- 2531kbps
- ベストアンサー率13% (183/1333)
http://www.google.co.jp/search?client=firefox-a&rls=org.mozilla%3Aja-JP%3Aofficial_s&hl=ja&q=%E7%B4%A0%E6%95%B0%E3%82%92%E5%88%A4%E5%AE%9A&lr=&btnG=Google+%E6%A4%9C%E7%B4%A2 http://www.ipa.go.jp/security/fy14/crypto/prime_num/invest.pdf 素数判定をたやすくできないからこそ、それを利用して暗号化技術があるのではないかな？ とすると、PCが暇なときに1から順に素数判定をしていき、それをテキストファイルにでも格納していく。 判定時はそれを検索すればよい。 もしそのときに、格納していない素数の判定リクエストが来たら、それを計算する。
お礼
ありがとうございました。
関連するQ&A
- 素数をみつける方法を教えて下さい
早速ですが、素数を少しでも楽に見つけ出す方法が知りたいです。 私はエラトステネスの篩「自然数NがNの平乗根を超えない最大の整数以下の全ての素数で割り切れなければ、Nは素数である」 は知っています。他にも素数を少しでも楽に見つけ出す方法を教えてください。
- ベストアンサー
- 数学・算数
- 中1です。500以上1000以下の素数を３つ探し、
中1です。500以上1000以下の素数を３つ探し、 それが素数であることを示してください。 それで、エラトステネスのふるいという方法を 教えてもらったのですが、 よくわからなかったので、 どなたかわかりやすく教えてください。 あと、まだルートを習っていないのでルートを使った式は わかりません・・・。 宜しくお願いします。
- 締切済み
- 数学・算数
- すばやく素因数分解する方法は？
「暗号解読」（サイモン・シン（著）青木薫（訳） 新潮社）という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数（合成数）を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法（素因数分解）を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法（アルゴリズム）を知りたいです。
- ベストアンサー
- 数学・算数
- 菅野正人の素数生成方法は、多項式時間計算量？
菅野が下の動画に示した素数生成メカニズムを形式化した、菅野著『数字パズル SeeK 10』などに於ける、エラトステネスの篩のアルゴリズムは、多項式時間内で素数を生成可能ですか。： https://www.youtube.com/watch?v=7u9NdEAOQaY
- ベストアンサー
- その他([技術者向] コンピューター)
- エラトステネスのふるい（素数）についての疑問
今、家にある中学の参考書を読みながら、中学数学を勉強しているものです。その中の素数についての一番最初の問題で、 次のうちから、素数を選べ。 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で終わっている理由が分からないのです。 馬鹿みたいな問題かもしれないのですが、頭が堅くて、分からなくて困っているので、良かったら教えていただければ嬉しいです…。
- ベストアンサー
- 数学・算数
- C言語 エラトステネスのふるい ポインタ
Ｃ言語のプログラミングなのですがどなたか教えて頂けませんか。（説明も） エラトステネスのふるいを用いて,10000 までの自然数に素数がいくつあるかを表示するプログラムを作れ。 ただし , 配列は用いず, ポインタを用いること メモリの確保には malloを使うこと よろしくお願いいたします。
- 締切済み
- その他（インターネット・Webサービス）
お礼
ありがとうございました。