- 締切済み
メルセンヌ数
Tacosanの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
p|Mp-1 だから.
関連するQ&A
- 素数 再帰関数
メイン #include<stdio.h> extern void count_primes(void); extern void print_primes(void); int max; int count; int primes[1000] int main(void) { printf("Uper limit: "); scanf("%d",&max); count_primes(); print_primes(); } 素数を求める(関数呼び出し) extern int nextprime(int n); extern int max; extern int count; extern int primes[]; void count_primes(void) { int i; count=0; for(i=2;i<=max;i=nextprime(i)){ primes[count++]=i; } リカーバシブ(次の素数) int nextprime[int n] { int i; for(;;){ n++; for(i=2;i*i<=n;i=nextprime(i)){ if(n%i==0) break; } if(i*i>n) break; } return n; } 素数プリント #include<stdio.h> extern int count; extern int primes[]; void print_primes(void) { int i for(i=0;i<count;i++){ if((i>0)&&(i%10==0) printf("\n"); printf(" %6d",primes[i]); } printf("\n素数の数 %d\n",count); } これら4つのモジュールで素数 nが求められますがアルゴリズム理解できません。この2つの関数のアルゴリズムについて、ご教授ください。め
- 締切済み
- C・C++・C#
- 素数 無限
「素数は無限にある」証明について。(たびたびすみません) 素数が有限個で n 個と仮定し 素数を P1, P2, P3, …, Pn とする P = (P1 x P2 x P3 x…x Pn) + 1 とおくと、 PはP1からPnで割り切れない ・・・理解できます。 従って、 Pは n+1 個目の新たな素数 ・・・★ここが理解できません。 Pは、1~P-1の数で割り切れないなら、素数(定義そのもの)ですが。 Pは、P1, P2, P3, …, Pn以外の合成数(素数以外の数)で割り切れる可能性もあると思います。 中学生ぐらいの証明のようですが、自分の頭の悪さに苦しんでいます。 2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509
- 締切済み
- 数学・算数
- 素数は無限
質問2点。 1. 「素数は無限に存在する」証明をwikipediaで調べると、 背理法で素数が無数にあることを証明した、 素数の積に1を加えた数が素数であることを証明した」などの誤解をする者がいるが、 いずれも正しくない と書かれています。 wikipediaが常に真実とは限りませんが、 Google検索で素数の無限である証明で検索すると、上記の誤解している人による解説ばかりです。 何を(どちらを)信じればよいか分からずに困っています。 2. wikipediaによる正しい証明によると、、、 素数の個数が有限と仮定し、p1, … pn が素数の全てとする。その積 P = p1 × … × pn に 1 を加えた数 P + 1 は、p1, …, pn のいずれでも割り切れないので、素数でなければならない。しかし、これは p1, …, pn が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無数に存在する。 これは、背理法による証明だと思うのですが、、、、 お手数ですが、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数定理をこのように解釈しても良いか。
素数定理とは、 「大きな自然数xが素数である確率は1/(log x)」 という物ですが、これを元に次の事が言えるでしょうか? 1 2と5を除けば素数は一の位が1,3,7,9の どれかになり、各グループの素数は無限個ある。 2 素数が現れる確率は4つのグループそれぞれで 等しい。 直感的にはどちらも正しいような気がしますが いかがでしょうか? 1に関してですが素数が無限個あることの証明は、 非常に簡単です。有限個だとしたらそれらの全ての 積に1を加えたものも素数になってしまうので 素数は、無限個あります。しかし各4つのグループ ごとにある事を証明しようとするとちょっと手が 止まってしまいます。 2は、完全にお手上げです。素数定理には、 一の位が何であるかで場合分けしていないので まぁ正しいような気がしますが。。。 どなたかご意見お願いします。
- 締切済み
- 数学・算数
- 素数は無限に存在する
素数が有限であると仮定し、その最大のものをNとする。 a、b、cを自然数とした場合、すべてのaについて N+a=b*cとなるb、cが存在する。 この式を変形すると N=b*c-aとなる。 ところがa=bの場合、aはNの約数となり最初の仮定と矛盾する。 よって素数は無数にある。 この証明は正しいのですか?というのはこの矛盾をつくことによって、有限ではない!!って感じがしないんですよね。a=bの時はNは素数ではない!!っていうのは分かるんですけど、a≠bでちょっと特別の場合(a=1,b=4,c=5など)は成立しちゃうんじゃない!?っていうのもあるし(aの値が変化することによってb、cの値も変化するだろうし・・・)、Nは素数ではないっていう証明をしただけで、「最大の」素数ではないって感じがしないんですよね・・・ こっちの証明は普通に納得するんですが・・・ 定理が成立しないとすると,素数は有限個である.それらの素数をP1,P2,P3,・・・,Pnとする.このとき,Q=(P1P2P3…Pn)+1を考えると, QはP1,P2,P3,・・・,Pnのどれでも割り切れない.したがって, Qを素数の積として表したとき,この積に現れる素数はP1,P2,P3,・・・,Pnのいずれとも異なる. これは矛盾である。したがって定理が証明された. なんかすっきりしなて非常に困ってます。誰か教えてください。お願いします。
- ベストアンサー
- 数学・算数
- 素数の分類と無限性に関して。
素数の分類と無限性に関して。 ※^は乗数の意味です。 8n+1型の素数が無限に存在することの証明 原始根の存在(素数 p を法とする整数環 Z/pZ の乗法群が位数 p - 1 の巡回群であること)を使う。 x を整数とする時x^4 + 1 の奇素数因子を p とする。 x^4 ≡ - 1 (mod. p) より、両辺を2乗することでx^8≡1となる。 x の p を法とする整数環 Z/pZ の乗法群での位数は 8 で有るから、 p ≡ 1 (mod. 8) となる。ここで、 p ≡ 1 (mod. 8) となる素数が有限個であったとする時、その総乗積を P として、 (2P)^4 + 1 の奇素数因子を考えると矛盾が出る。 私は2PをX"とおいて上と同様に考えました。 この証明の流れや、8n+1型の素数が無限に存在することは理解できるのですが、上の証明における「位数は 8 で有るから、 p ≡ 1 (mod. 8) となる」の部分がどのようにして言えるのかが分かりません。フェルマーの小定理を用いているのでしょうか? よろしくお願いします。
- ベストアンサー
- 数学・算数
補足
もう少し詳しくお願いします(>_<)