素数

以前新聞で素数の配列の規則性が見つかっていないという
記事を見つけました。
自分で考えたんですけど縦横に
数字をランダムに決めます。(１×は無し)その四角形にパネルを
その数だけ置きます。まず横を２と決め縦を何でも好いのでAと
決めます。そして、その縦に一個だけパネルを増やします。
そこから、こんどは横を3つにしA＋１個のパネルを
３っつずつ乗せていきます。この作業を横＝縦になるまでやっても
ピッタリ当てはまらなかったら。それは素数だと決めてよいので
しょうか？
しかし、そんなに規則性が見つからないものなのでしょうか？

No.4 ベストアンサー 回答者： zk43 回答日時： 2007/02/14 20:10

文章の正確な意味はわかりませんが、おそらく長方形に並べることが

出来なければ素数だと言っているのだと思います。
これは縦横が約数ですから、本質的には約数を探す、エラトステネス
のふるいと同じ事だと思います。
小さい数に対しては良いですが、何万桁、何百万桁となっては現実的な
方法ではありません。ある数が素数かどうかを判定する方法は、詳しく
は知りませんが、リュカ・テストとかいくつか有効なものがあるそうです。
現在見つかっている最大の素数は９８０何万桁だかの素数だそうです。
Great Internet Mersenne Prime Search(GIMPS）という組織だか何だか
が、世界中のパソコンに計算を分散させて、計算を行っているようで
す。１年に１個か２個くらいのペースで記録が更新されています。
おもに、2^n－1の形の数が素数かどうかを調べているようです。
（Mersenne数）
次に見つかるのがおそらく初の１千万桁超えの素数だと思います。
大きい素数は、暗号などにも利用されるようです。

この回答へのお礼

ご回答ありがとうございました。

お礼日時：2007/02/14 22:05

No.3 回答者： ojisan7 回答日時： 2007/02/14 18:21

「縦横に数字をランダムに決める」ということですが、意味がよくわかりません。

しかし、素数判定はエラトステネスの方法のように１つ１つ素数を拾っていくか、さもなければ、短時間で素数を判定するアルゴリズムを工夫しなければなりません。現在までのところ、素数判定のアルゴリズムは、いくつか知られていますが、かなり複雑です。実際の計算は、そのアルゴリズムを用いて、何時間もコンピュータを稼働して判定するのです。現在、どのようなアルゴリズムが使われているかは、インターネット等で検索してみてください。ともかく、質問者さんの掲げた、単純なアルゴリズムでは、素数判定が無理だということは、確実です。

この回答へのお礼

エラトステネスという人が初めにやったんですね。

ご回答ありがとうございます。

お礼日時：2007/02/14 22:04

No.2 回答者： nuruo 回答日時： 2007/02/14 16:37

私も興味があるので，次の疑問に答えてもらいたいのですが．

縦横に数字をランダムに決めるとは？
その数とはどの数？

まずはこの２つについて教えてください．

No.1 回答者： byubyu9999 回答日時： 2007/02/14 04:55

もし、その方法があってるとしたら、歴史的な発見ですね。

しかし、なんか説明がわかりにくいのだけど、
もう少しわかりやすく書けませんか？

まったくイメージがわかないのですが。

この回答へのお礼

ではもう一回書きます。

お礼日時：2007/02/14 22:02