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


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

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

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

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

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

回答の条件
  • 1人50回まで
  • 登録:2015/01/26 18:53:46
  • 終了:2015/01/29 18:51:53
id:Gasyou

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

回答(3件)

id:language_and_engineering No.1

lang_and_engine回答回数170ベストアンサー獲得回数632015/01/27 00:05:06

ポイント45pt

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

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

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

id:yoneto164 No.2

ヨネちゃん回答回数813ベストアンサー獲得回数942015/01/27 02:45:01

ポイント10pt

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

id:practicalscheme No.3

practicalscheme回答回数157ベストアンサー獲得回数422015/01/27 04:06:53

ポイント45pt

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

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

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

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

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

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

id:yoneto164

凄いですね、当方は 128M でしたのでそこまで処理できませんでした。

2015/01/27 13:35:32
  • id:language_and_engineering
    こんにちは。質問カテゴリがネタ・ジョークなので,どうコメントしたものか悩んだのですが,,

    もうすでに知っておられることで,恐らくこの質問の前提になっている事柄だとは思うのですが
    一応コメントさせていただきます。


    ・「x未満の素数の数」とは,つまり素数計数関数π(x)のことである。
    この関数の性質はいまのところ漸近的に,低精度でしかわかっていない。

    ・もしπ(x)の漸近的な振る舞いを高精度で知りたい場合は,まずリーマン予想を解決する必要がある。

    ・質問は,π(x)の値を漸近的どころか,厳密に得られることを前提に問われている。つまり,リーマン予想の解決よりも,さらにだいぶ先の質問である。

    ・π(x)の厳密な振る舞い,およびπ(x)の厳密値の構成方法が現在知られていない以上,「π(x)の値が素数であるかどうか」を判別するすべも今のところ存在しない。

    ・ところが,この質問には「回答には「Nを求める為のアルゴリズム」の記述を必須とします。」とある。なので,この質問に回答できる人はいない・・・。


    ということなのですが,総当り法ではダメなんでしょうか・・・
  • id:language_and_engineering
    ちょっとだけ訂正
    ・π(x)の厳密値の構成方法が現在知られていない以上,

    ・π(x)の厳密値のエレガントな構成方法が現在知られていない以上,
  • id:Gasyou
    えっと、すいません、そこまで深く考えていませんでした。
    質問文に「条件2の判定には総当り法を使用してもOKです。」を追加します。

    条件1~3の判定全てに総当り法を使用するのであれば、自分でコードを書いてしまえばいい話ですので、「何か面白い解法がないかな」と思って質問した次第です。
  • id:ita
    ちょっとズルい方法ですが、検索するとpi(x)の値はいろいろ落ちています。
    http://sweet.ua.pt/tos/primes.html
    ここでたとえば2^31以下の素数の数を知って、そこから数を減らしていって素朴に一個ずつ素数判定していって、素数の数を減らしていって素数の数が素数になったらそこで終了とすると一瞬で終わりました。
    ちなみに64 bit以下という条件にすると
    p=8589931561 pi(p)=425656284035217607
    です。

    >||
    #include <stdio.h>
    #include <stdlib.h>

    int is_prime(unsigned long long n)
    {
    if((n&1)==0)return 0;
    int i;
    for(i=3;i*i<=n;i++)
    {
    if(n%i==0) return 0;
    }
    return 1;
    }

    int main(int argc, char **argv)
    {
    unsigned long long nprime= 105097565;
    unsigned long long n=(1LL<<31)-1;
    unsigned long long i;

    for(i=n;;i-=2)
    {
    if(is_prime(i)==1)
    {
    nprime--;
    if(is_prime(nprime)==1)
    {
    printf("p=%lld np=%lld\n", i, nprime);
    exit(1);
    }
    }
    }
    }
    ||<

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません