- ベストアンサー
素数をみつける方法を教えて下さい
早速ですが、素数を少しでも楽に見つけ出す方法が知りたいです。 私はエラトステネスの篩「自然数NがNの平乗根を超えない最大の整数以下の全ての素数で割り切れなければ、Nは素数である」 は知っています。他にも素数を少しでも楽に見つけ出す方法を教えてください。
- 数学・算数
- 回答数4
- ありがとう数1
- みんなの回答 （4）
- 専門家の回答
関連するQ&A
- 素数を判定するいろんな方法は？
素数を判定する方法はエラトステネスのふるいの他に何かあるのでしょうか。１００までは大抵の本に載っていますが、大きな数はふるいにかけても、膨大な手間がかかりそうです。
- 締切済み
- 数学・算数
- 中1です。500以上1000以下の素数を３つ探し、
中1です。500以上1000以下の素数を３つ探し、 それが素数であることを示してください。 それで、エラトステネスのふるいという方法を 教えてもらったのですが、 よくわからなかったので、 どなたかわかりやすく教えてください。 あと、まだルートを習っていないのでルートを使った式は わかりません・・・。 宜しくお願いします。
- 締切済み
- 数学・算数
- 平方数でない整数の平方根は無理数であることの証明
すみません。高齢者なので使用する文字はすべて正の整数とします。 整数の平方根で整数になるのは1,4,9,16のような平方数だけです。例えば5の平方根を考えた場合、 4の平方根は2、 9の平方根は3ですから、5の平方根は2と3の間の数となり絶対に整数にはなりません。以上は単なる確認です。 そこで平方数ではない整数をaとします。これの平方根を√aと表記します。確認通り√aは整数にはなりません。この非平方数の平方根が分数で表現できるかどうかが問題です。 √a=n/mと分数で表現できるとします。ここでｎとｍは互いに素であるとし、当然ｍ≠1です。 両辺を2乗すると a＝ｎ2/ｍ2 となります。ここでaは整数です。ｎ2とｍ2にも共通の約数はないので、ｎ2/ｍ2は整数にはなりません。すると左辺は整数、右辺は小数（小数点以下が0ではない純粋の小数）になるのでこれは矛盾です。従って平方数ではない整数の平方根は全て無理数である。 質問は、こんなに簡単な証明でいいのだろうか？基本的なところで考え方に穴があるのではないだろうか？ということです。ご教示願います。
- ベストアンサー
- 数学・算数
- 素数の判定
自然数Nが√Nを越えない最大の整数以下のすべての素数で割り切れなければ、Nは素数である。 この定理の証明について、わからないことがあるので質問します。本の証明では√Nを越えない最大の整数をnとし、Nがnより大きい素数qで割り切れたとすると、そのときの商をpとして、N=pqである。ここで1<p≦n＜q<Nに注意すると、 pが素数ならNは素数pで割り切れるはずだし、pが合成数ならNはpの素因数で割り切れていたはずであり、いずれにしても不合理である。証明終わり。 自分は不合理を示す証明は、背理法を使っていると思ったのですが、その場合自然数Nが素数でないと仮定して証明を始めると思いました。しかし√Nを越えない最大の整数をnとし、Nがnより大きい素数qで割り切れたとすると、という仮定で始まっています。また√Nを越えない最大の整数をnとし、Nがnより大きい素数q以外では割り切れないとすると、という文章の解釈でよいのかと思いましたが、はたして正しい証明なのか疑問が残りました。最後に対偶をとってそれを背理法で証明しているのかと思いました、対偶は、Nが素数でないならば、√Nを越えない最大の整数をnとし、Nはn以下の素数いずれかで割り切れる。ですが、これを背理法で証明しようとすると、 Nはn以下の素数いずれかで割り切れない、という仮定から始まるとおもいました。本の証明の書き出しと違いました。自分で考えた方針では、本の証明とだいぶ違います。 だれか本に書かれた証明で、pで割り切れると何が不合理なのかと、自分の証明の方針のまちがいを指摘してください、お願いします。
- ベストアンサー
- 数学・算数
- エラトステネスのふるい java
下の問題がわかりません。どうかよろしくお願いします 問1 2以上ｎ以下の自然数のうち、素数だけを選び出し、prime.txtという名称のファイルに書出したい。ただし、ｎの最大値は2^15 - 1 = 32767とする。 これをエラトステネスのふるいによって書きなさい 問2 上記の方法で作成したprime.txtを利用して、キーボードから入力する適当な自然数lを素因数分解するプログラムを作成しなさい。
- 締切済み
- Java
- #include<stdio.h>
#include<stdio.h> #include<math.h> int main(void) { int i,n,limit; printf("data? "); scanf("%d",&n); i(n>=2){ limit=int)sqrt(n); for(i=limit;i1;i--){ if(n%i==0) break; } if(i==1) printf("素数\n); else printf("素数でない\n"); } return 0; } というプログラムがあるのですが、それを改良して int型(符号付32ビット整数)および、unsigned int型(符号なし32ビット整数)のそれぞれの最大の素数を求めよという問題があり、ただし、エラトステネスのふるいは使わずに、上のプログラムを改良してみよという問題がどっかにあったんですが、全然わからないので、教えてください。
- ベストアンサー
- C・C++・C#
- P(n)をnの最大の素因数としたとき、
整数論の問題です。 整数n≧1に対して, P(n)をnの最大の素因数とします。 このとき, P(n^2+1)→∞(n→∞)となる。 n≧240ならばP(n^2+1)≧17となる。 のですが、どうしてでしょか？ さらに、P(n)≦7, P(n+1)≦7となる整数nを全て求めると、どうなるでしょうか？
- 締切済み
- 数学・算数
- エラトステネスのふるい（素数）についての疑問
今、家にある中学の参考書を読みながら、中学数学を勉強しているものです。その中の素数についての一番最初の問題で、 次のうちから、素数を選べ。 1 6 13 25 51 79 87 91 という問題があり、その解法の一つでエラトステネスのふるいというもの（2から順に自然数を書き、2を残して2の倍数を消し、3を残して3の倍数を消し、5を残して5の倍数を消す、以下同様にして求める…という方法）があるのですが、上の問題でずっとエラトステネスのふるいを使いながら合成数を消していくと、11の倍数を消すところで、「13、79は11で割り切れず、13÷11、79÷11ともに商が11より小さくなるから素数である。」と参考書にあり、そこでふるいをかける作業は終わっています。 この参考書（特に、"13÷11、79÷11ともに商が11より小さくなるから素数である。"というところ）のこの部分と、ずっとにらめっこをしてきたのですが、何故「13÷11、79÷11ともに商が11より小さくなるから素数である」と言い切れるのか、分かりませんでした…。 少なくとも13は、次に11の倍数となる数である11×2=22の間に13が存在しないから素数、と言い切れる感じはするのですが、79だと、たとえ11で割り切れなくても、13、17で割り切れるかもしれない…（もちろん実際そんなことはないのですが）、と、感覚的にそう思ってしまいます。そして、「13÷11、79÷11ともに商が11より小さくなるから素数である」を言いかえれば、「商が11より大きくなる場合は、素数でない可能性がある（121以降の数であれば、たとえ今の時点で11で割り切れなくても、素数でないかもしれない）」というのも、よく分かりません…。 そんなこんなで、このふるいが11で終わっている理由が分からないのです。 馬鹿みたいな問題かもしれないのですが、頭が堅くて、分からなくて困っているので、良かったら教えていただければ嬉しいです…。
- ベストアンサー
- 数学・算数
