人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

とある3つの条件を全て満たす、可能な限り大きな自然数を教えて下さい。

条件は下記の通りです。
なお、「条件を満たす自然数」をNと表記します。

1)Nは素数である。
2)N未満の素数の数が素数である。
3)Nは2,147,483,647(符号付き32ビット整数の最大値)以下である。

例えばN=5の時は上記の条件を全て満たしますが、N=11は条件2を満たしません。

回答には「Nを求める為のアルゴリズム」の記述を必須とします。
また、ポイントはNの大きさに応じて傾斜配分し、同じNが2回以上回答された場合は、先着順とします。

ちょっと気になって質問しただけですので、お気軽に回答頂ければと思います。

●質問者: 森岡@GA将!!!!!!!!!
●カテゴリ:科学・統計資料 ネタ・ジョーク
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

質問者から

追伸 「1から順に総当りで求める」というアルゴリズムは除外させて頂きます。
エレガントな回答をお願いします。


1 ● lang_and_engine
●45ポイント

まず,素数を列挙して配列とする。
その配列内の,「素数+1番目」の要素を返せばよい。
(終わり)

コメント欄で難しいことを書いてしまってごめんなさい。
こういうことですよね。

[2,3,5,7,11,13,・・・]
という配列の,2+1番目=5, 3+1番目=7,5+1番目=13,・・・


2 ● ヨネちゃん
●10ポイント

PHPで素数をリスト化しましたが、メモリが足りず2,631,000あたりまでしか走りませんでした。
Array ( [0] => 2 [1] => 3 ・・・ [191953] => 2630951 [191954] => 2630989 )
となりましたので、素数 2,630,951 未満の素数の数は 191,953 で素数。
メモリを増やしてまたやってみます。


3 ● practicalscheme
●45ポイント

あっさり見つかりました。
とはいえ、実質的に「総当たり」なので回答条件を満たしているかどうかは微妙です。

N=2147483579、N未満の素数の数=105097561

求めた手法:
2^31-1以下の素数の逆順リストを用意し、先頭から「その要素以降の要素数が素数になっているか」を調べて最初に見つかったものが答え。

コードはこちら (Gauche Schemeです):
https://gist.github.com/shirok/9d271de7c59292a45a11

Core i7, 16GBのマシンで2分くらいでした。素数のリストを作る時間がほとんどで、探索は一瞬です。

メモリの余裕があまりなかったので、上限が増えるとこの手法ではつらいですね。コメント欄にあるようにπ(x)を厳密に求めるには何らかの形でそれ以下の素数の情報をとっておくのが一番なので、大きい改善は思いつきません。定数倍の改善でしたら、「N以下の素数の数が偶数なら最初から除外できる」ことからリストを1個飛びに保存しておくとか、もう少し工夫してトリビアルな合成数番目の要素は保存しないとかできそうですが。


ヨネちゃんさんのコメント
凄いですね、当方は 128M でしたのでそこまで処理できませんでした。
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ