プログラミングと素数砂漠

素数砂漠の最大値を求めるプログラムをBASICで作りたいのですが・・
数学もプログラミングも大の苦手で全く分かりません；
どなたか知恵を貸してくださいませんか？？

No.7 ベストアンサー 回答者： proto 回答日時： 2010/02/08 09:43

まず「素数じゃなかったら」とか言ってるとだんだん混乱してくるので、「合成数」という言葉を使いましょう。

素数砂漠とは、自然数列のなかで合成数が長く続く部分ですね。
で、素数砂漠の"最大値"と言うからには、合成数がいくつ連続するか、"いくつ"という部分に興味があるわけです。


例えば1から13までなら、
　 1,2,3,[4],5,[6],7,[8],[9],[10],11,[12],13
と、括弧を付けた数が合成数ですね。
見たところ8から10までで3個合成数が連続しています。
それ以外の部分は1個の合成数が連続するだけです。
(1個で連続するというのも言葉としておかしくはあるが…)
結局、この場合なら素数砂漠の最大値は3というのが妥当な答えでしょう。
これだけでもかなりイメージ出来たのでは無いでしょうか？

まず、『最初に素数Aを入力してもらって、A-1、A-2、・・の数を素数判定していって初めて「素数でない」という判定がでた数が素数砂漠の最大値？になるのかな』という、この方法ではダメですね。
13から始めた場合、前の13-1=12は合成数、もう一つ前の13-2=11は素数で、ここまでで判定を終了してしまうと合成数が連続するのは1個だけという事になっていしまいます。
ですが、先ほど見たように合成数が3個連続するのは8～10の部分です。
11まで調べてやめてしまってはいけないのです。

数Aを入力してもらい、1～Aまでの範囲で考えるというのは良いでしょう。
Aが大きくなれば顕著になるのですが、1～Aまでの自然数列の中で最大の素数砂漠がどこにあるのか、最初の方にあるのか最後の方にあるのか、それは調べる前にすぐ分かることではありません。
数が大きくなるほど素数の割合は減っていくので後半ほど素数砂漠が大きくなる傾向はあるのですが、Aの直前の部分が最大の素数砂漠であるとは限りません。


以上のことを踏まえてアルゴリズムを考えてください。
簡単に言ってしまえば、
・1からAまでの数について素数か合成数かをひとつひとつ判定していく。
・素数で区切られた区間について、合成数が連続する数を区間ごとに数える。
・それらの中で一番大きな区間(最大の素数砂漠)の長さを出力する。
こんな感じになるでしょう。

理屈としてはこのようにすれば素数砂漠を探すことはできます。
しかしプログラミングをする上では、
　　Aが大きくなれば素数で区切られた区間を保持するテーブルも大きくなること
　　判定しようとする数が大きくなれば素数判定にかかる時間も大きくなること
これらを考慮してメモリと時間を節約するアルゴリズムを考える必要があるでしょう。

この回答への補足

なるほど！
私は「素数砂漠の最大値」＝「そこまでに存在する合成数の中で一番大きな数」だと勘違いしていたみたいです。
挙げてくださった例で言うと「12」だと思ってました。
分かりやすくて丁寧な説明ありがとうございます。
理屈は理解できました！
理屈は、なところが私の頭の残念なところですが・・
これらのことを踏まえながら考えてみようと思います。
本当にありがとうございました！

補足日時：2010/02/08 16:55

No.6 回答者： tsukita 回答日時： 2010/02/08 04:37

こんばんは。

ことばで表現するのが難しいようですので・・・

例えば、あなたのプログラミングした関数（？）に
１、２、３、４、５
を入力した場合（初期値を与えた場合）の出力はどうしたいのですか？

この回答への補足

protoさんのアドバイスにより、自分が「素数砂漠の最大値」を勘違いしていたことに気づきました；
今頭の中にあるプログラムじゃ全然ダメなことが分かったので、もう1度考えさせてください。
とりあえず最初は自分でやってみますね。
たくさんのアドバイスありがとうございました！
分からなくなったらまたここに来ると思うので、その時はまたよろしくお願いします。

補足日時：2010/02/08 17:09

No.5 回答者： koko_u_u 回答日時： 2010/02/07 22:58

>今私の頭の中にあるプログラムを書きだしなさいということですか？？

そうじゃない。
例えば、素数 p をプログラムに与えて「素数砂漠」をどのようなフォーマットで得たいのですか？
プログラムに与えられた数が素数でない場合はどうするのですか？

この回答への補足

最初に素数を入力してもらって、一応素数判定を行い、素数じゃなかった場合は「入力ミス」等の表示をしたいと思っています。
素数だった場合は、先ほど補足したように数字を1つずつ遡って素数判定をし、「素数でない」数が出たらそれが素数砂漠の最大値になるのかな？と考えたんですが・・・
よく考えてみれば、入力した素数がAでA-1も素数だとしたら素数砂漠は存在しないことになるんですかね？；
プログラムを「入力した素数までに存在する素数砂漠の最大値」とすればいいんでしょうか？

補足日時：2010/02/07 23:15

No.4 回答者： koko_u_u 回答日時： 2010/02/07 22:22

>連続して素数が現れない部分＝「素数砂漠」らしいです。

そうだとして、貴方が求めるプログラムの入力とその出力はどのようなものになりますか？

この回答への補足

えっと、今私の頭の中にあるプログラムを書きだしなさいということですか？？

補足日時：2010/02/07 22:45

No.3 回答者： koko_u_u 回答日時： 2010/02/07 21:05

>最初に素数Aを入力してもらって、A-1、A-2、・・の数を

>素数判定していって初めて「素数でない」という判定がでた数が
>素数砂漠の最大値？になるのかな～と思ったんですが・・

要するに、素数 p の「手前の」素数 q を「素数砂漠」と呼んでいるということですか？

この回答への補足

連続して素数が現れない部分＝「素数砂漠」らしいです。

補足日時：2010/02/07 21:17

No.2 回答者： qaz_qwerty_me 回答日時： 2010/02/07 19:33

試験問題の丸投げは違反ですよ！！

WIKIから
1とその数自身以外に正の約数がない1 より大きな自然数のこと。

どこまでの範囲で調べるかを決めないと無限大になると思います・・・

この回答への補足

ごめんなさい；
何が分からないかも分からない状態だったので；

最初に素数を入力してもらう形のプログラムにしようと思ってます。

ご指摘ありがとうございました！

補足日時：2010/02/07 20:11

No.1 回答者： koko_u_u 回答日時： 2010/02/07 19:01

「素数砂漠の最大値」をもっと具体的に定式化するところから始めましょう。

はい、補足にどうぞ。

この回答への補足

具体的に定式化、ですか？

ええっと・・
素数は2以上の自然数で1とそれ自身以外の約数をもたない数で・・
自然数をNとすると2～N-1までの自然数で割り切れるかどうかで素数判定をするんですよね？？
だったら、最初に素数Aを入力してもらって、A-1、A-2、・・の数を素数判定していって初めて「素数でない」という判定がでた数が素数砂漠の最大値？になるのかな～と思ったんですが・・

定式化できませんでした；すみません；

補足日時：2010/02/07 20:17