• ベストアンサー

整数問題

　nを自然数としたとき、n^2+1が素数となるようなものは何個あるか。 　このままでは解けないと思いますが、鬱陶しいことに10^14（十兆）までの間に、いくつ見つかるかというのが重要なようで、算出のアルゴリズムがあれば教えてください。 　素数表でチェックするというのでは、駄目なようです。 　これを要求してきているのは、鍵メーカーです。

noname#82774
noname#82774

質問者が選んだベストアンサー

  • ベストアンサー
  • PRFRD
  • ベストアンサー率73% (68/92)
回答No.1

n^2 + 1 ≦ 10^14 でしょうか．それとも n ≦ 10^14 でしょうか． エレガントなアルゴリズムは無いと思いますが， もし前者だったら，単純な方法で簡単に求めることができます． （後者だと，それなりに待たないと，ダメかもしれません） 実際，今 「n を順番に増やしながら n^2 + 1 が素数かどうかを確率的素数判定法で調べる」 という方針でやってたみところ，私のPC（CPU: 1GHz）で，数分程度で計算でき， 全部で456362個になりました． ＃確率的素数判定法としてはMiller-Rabin法の脱乱択化したものを用いており， ＃この範囲の数なら，厳密に素数性を確かめることができています．

noname#82774
質問者

お礼

　ご回答ありがとうございます。 　おお、速いです。456362個ですね、ともかくそれを連絡します。ありがとうございました。

noname#82774
質問者

補足

　前者の場合です。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 整数問題？がわからないので教えてください

    nが自然数であるとき、n(n^3-1)(n^3+1)は偶数で、かつ7の倍数であることを示せ。 という問題なのですが、 nを奇数とするとn=2k+1(kは自然数)とおけ、与式=4k(2k+1)(4k^2+6k+3)(4k^3+6k^2+3k+1) までやってみましたが、よくわからないので、解答をお願いします。

  • 整数問題

    問題文は省きます。 nは自然数です。 証明の過程で、n=3k＋1のとき、 「n＋2=(3k＋1)＋2=3(k＋1)が合成数である」ことを示したいのですが、上のn=3k＋1の式で、k=0としてもn=1となるので、nは自然数であることを満たしてますよね。 しかし、命題「n＋2=(3k＋1)＋2=3(k＋1)が合成数である」については、k=0とするとn＋2=3となってしまい、合成数にはなりません。 参考書では、kは整数とし、「n＋2=(3k＋1)＋2=3(k＋1)は合成数である」と断定しているのですが、答案を書く際これで本当にいいのでしょうか。 回答よろしくお願いします。

  • 整数問題です。

    「l,m,nが自然数のとき l+1/l+m+1/m+n+1/n=k も自然数になるという。このようなkの値をすべて求めよ。」 という問題なのですが、不等式を作るんじゃないかなとは思うのですが、解けません。どなたか教えて下さい。よろしくお願いします。

  • 整数問題について

    適当ですが、例えば「全ての自然数nについてn^3＋5nが3の倍数であることを示せ」 という問題があれば、n=3k、n=3k±1とおいて式に代入しますよね。 整数問題を扱った参考書を見ると、k:整数として置いているのですが、 n^3＋5nに実際にn=3kを代入し、 n^3＋5n=3(kの式)となっても、kは整数という条件なのでこれにk=0を当てはめれば0になってしまいます。 質問(1) 上の説明 質問(2) k:自然数　とおいて議論を進めても減点はされないのか よろしくお願いします。 もしかすると0も3の倍数…？

  • 整数問題です

    nが自然数のとき、5^6n + 5^4n + 5^2n + 1を13で割った余りを求めよ という問題で、 解）(mod13)とする 　　5^2＝25≡-1より 　　(与式)≡(5^2)^3n + (5^2)^2n + (5^2)^n + 1 　　　　　≡(-1)^3n + (-1)^2n + (-1)^n +1 　　　　　≡2(-1)^n +2 　　　　　≡4　(n:偶数)， 　　　　　　0　(n:奇数) というものなのですが、 ４行目まではわかるのですが、 ５行目の 『　≡2(-1)^n +2』 になる理由がわかりません＞＜ わかる方、ぜひおしえてください。

  • 整数問題◆この答案で本当にいいの？

    昨日も質問したのですが、「問題がないと」という指摘があったので、再度問題文も掲載して質問させて頂きます。 問題： nを自然数とする。n，n＋2，n＋4がすべて素数であるのはn＝3の場合だけであることを示せ。 n、n＋2、n＋4 1 3 5 2 4 6 3 5 7 4 6 8 5 7 9 6 8 10 答案： 1)n=3のとき、確かにn，n＋2，n＋4は全て素数となる。 2)n≠3のとき、n，n＋2，n＋4のうち少なくとも１つが合成数であることを示すために、n≠3のとき、n，n＋2，n＋4全てが素数となると仮定してその矛盾を示す。 （上表より、全ての場合において3の倍数があるから、） n=3k、3k＋1、3k＋2（ｋ：整数）とかける。 ここから、実際に上3式をn，n＋2，n＋4に代入して矛盾を示していきます。 ◆質問はここから… n=3k＋1のとき、 参考書では，「n＋2=(3k＋1)＋2=3(k＋1)　これは合成数である」 となっているのですが、k=0のときは、 n＋2=(3k＋1)＋2=3(k＋1)=3なり、これは素数です。 k=1,2,3・・・のときは確かに合成数になりますが、k=0のときは素数。 答案を書く際、（ただしk≠0)と書いておかなくてはダメですよね？ 参考書ではそのような注意がないのです。 昨日質問した際、 「問題文が書いてないのは辛いが、当然にも、k＝1、2、‥‥である。」という回答を頂きました。 しかし、n=3k＋1とした場合、nは自然数なのでkは負にこそならないものの、k=0のとき、n=1となり自然数であることを満たします。 何か私がとんでもない勘違いをしているだけでしょうか…。 回答よろしくお願いします。 参考までに、昨日質問したページのURLを貼っておきます。 http://oshiete1.goo.ne.jp/qa4526910.html

  • 整数問題・・・

    わかりません・・・おしえてください・・できるだけわかりやすく・・くわしく・・・おねがいします・・ ２ｘ(2乗)－ｍｎｘ＋ｍ＋ｎ＝０　の解が自然数のとき　自然数ｍ、ｎを求めよ

  • 整数の問題を解いて下さい。

    次の定数、変数、添数は、すべて自然数であるとします。 以下の方程式が成り立っているとき、ｎ < ｋ[n+1] であることが証明できますでしょうか。 m1＊x1^k1 + m2＊x2^k2 + ... + m[n]＊x[n]^k[n]　=　 m[n+1]＊x[n+1]^k[n+1]. 宜しく御願い致します。

  • 整数の問題

    次の問題が解けなくて困っています。 nは自然数である。 (1)nが4の倍数のとき、n=x^2-y^2を満たす整数x,y(x>y≧0)があることを示せ。 (2)nが奇数のとき、n=x^2-y^2を満たす整数x,y(x>y≧0)があることを示せ。 どうか分かりやすい解説よろしくお願いします。

  • センターの整数問題

    こんばんは。センターの模試で質問があります。こんな問題です。 M、Nは自然数として、 「Mが2の倍数でかつ3M+2Nが6の倍数でない」ならば「N^2＋αは3の倍数」が真であるような2桁の自然数αは□□個ある。 解答は、2Nが6の倍数でないからNは3の倍数でないということに注目してN＝3L＋－1（L整数）だからN^2＋α＝3（3L^2＋－2L）＋1＋α として求めてます。確かにこれで解けますが、なぜ突然Nの倍数性に注目しようとしたのでしょうか？ すみませんが教えてください！

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する