- ベストアンサー
正整数Nの最大の素因数を求めるアルゴリズム
正整数Nの最大の素因数を求めるアルゴリズムがわかりません。 ネットで検索して一応出てきたのですが、どうしても理解できません。 int i,no=N; //Nは正整数 for(i=2;i*i<=no;i++){ while(no%i==0) no/=i; } iまたはnoのどちらかに求めたい素因数が入っています。 なぜこれで求めることができるのでしょうか？ noやiが非素数ということもあり得るのでは？ ずっと考えましたがわかりません。 誰か教えてください。
- 数学・算数
- 回答数5
- ありがとう数1
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
ANo.4で参考に挙げた知恵袋の質問が消えそうなので そちらで紹介した代替案を転載します ---- こんな方法ではどうでしょう？ int no = N; int i, p = 1; // iは素因数候補, pは各段階での最大素因数 for(i=2;i*i <= no;i++){ if(no % i == 0){ p = i; // より大きい素因数が見つかったので, 最大素因数を更新する while(no % i == 0) no /= i; // noを素因数候補iで割れるだけ割る } } // no = 3*7のように最大素因数が√noより大きい場合は最後のnoが最大素因数 if(no > p) p = no; 最後にはpにNの最大の素因数が入っていることになります しくみは以下のとおり noが素数か1になるまで素因数候補i で小さいものから順に割り続けます すると素因数候補i が合成数の場合には絶対にnoを割り切れなくなります ですので noの最大の素因数は, 素数になったときのnoか最後にnoを割り切った数のどちらかです あとは, noと最後にnoを割り切った数pを比較して大きい方を選べば 最大の素因数が得られることになります ----
その他の回答 (4)
- tar0_puzzle
- ベストアンサー率100% (1/1)
リンク先の質問でも答えたのですが このアルゴリズムは, iもnoも非素数になる場合があります Nが素数のべき乗になっている場合です 例えば N=81 (3の4乗)の場合です iとnoの値を追いかけてみます まず int i,no=81; のように変数に値をセットして, for文の繰り返しを実行します i=2のとき, 2*2 <= 81なので, forのカッコ内を処理する 81 % 2 != 0なので, whileのカッコ内の処理をしない i=3のとき, 3*3 <= no (=81)なので, forのカッコ内を処理する 81 % 3 == 0なので, whileのカッコ内の処理(no = 81/3 = 27)をする 27 % 3 == 0なので, 同様にno = 27/3 = 9をする 9 % 3 == 0なので, 同様にno = 9/3 = 3をする 3 % 3 == 0なので, 同様にno = 3/3 = 1をする 1 % 3 != 0なので, whileのカッコ内の処理をしない i=4のとき, 4*4 > no (=1)なので, forのカッコ内を処理しない となって, 繰り返しが終了します このとき i=4, no=1 ですが, これらは81の最大の素因数ではありません
- nattocurry
- ベストアンサー率31% (587/1853)
a<b<cで、c=a*bだとして、i=cになった時点で、noは素因数にaもbも含まない状態になっているので、aとbの積であるcも当然noの素因数には含まれません。 なので、no%i==0の条件を満たすことはなく、no/=iの処理も行われません。
- nattocurry
- ベストアンサー率31% (587/1853)
Nが素数なら、2<=i<=√Nの範囲で、whileループ条件であるno%i==0にあてはまるiは存在しないので、no/=iは実行されることがなく、no=Nのまま終了します。 whileループでは、一度no%i==0の条件に当てはまったら、そのiでnoが割り切れなくなるまで繰り返します。 それを、i*i<noの条件を満たす限り、iを大きくしながら繰り返します。 noを割り切れるiがなくなったら、終了。 終了した時点で、noを割り切れるi(素数)がないんだから、noは素数ですよね。 iは2から1ずつ大きくしているから、iが非素数であることはありますが、forループでiがそんな値になったときには、whileループ条件のno%i==0には当てはまらないようになっています。
- Tacosan
- ベストアンサー率23% (3656/15482)
まず, ちょっと考えれば ・2以上 √N 以下のどの整数でも割り切れないなら N は素数 であることがわかります (N = pq とおくと p と q の一方は √N 以下). また, ・N を割り切る (2以上の) 最小の整数が素数 であることも簡単にわかります (素数でないと仮定して背理法が簡単?). だから「no や i が非素数」ということはありえません.
関連するQ&A
- 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を全て求めると、どうなるでしょうか？
- 締切済み
- 数学・算数
- 素因数分解の問題
久々に素因数分解の問題を解いてみようとしたところ、いきなり躓いてしまいました。 二桁の整数ｎに１６８をかけると、ある数の二乗になりました。この整数ｎはいくらになるかという問題です。 １６８を素因数分解し、ｎ×１６８＝ｎ×２＾３×３×７となることは分かります。 これから先、どのように組み立てて解けばよいのか分かりません。 解説では、各素数が偶数個になるように解くと書かれており、ある数の二乗になるため、 ｎ＝２×３×７×ｍ＾２となっていました。 どうしてこのような式なるのですか？ A＝A＾p×ｂ＾q×c＾rとなっている時、各指数がすべて偶数（２の倍数）なっていれば、Aは何かの二乗になることは確かめてみました。
- ベストアンサー
- 数学・算数
- ｎ^2－２０ｎ＋９１が素数となる整数ｎの値・・・
すごく、基本的な問題だと思うのですが、考え方に疑問があります。 ｎ^2－２０ｎ＋９１が素数となる整数ｎの値を求める問題です。 参考書の解説には、題式を因数分解して＝（ｎ－７）（ｎ－１３）とし、 Ｐが素数のとき、素因数分解したとき１×Ｐにしかならないので、 ｎ－７又はｎ－１３のどちらかが１ということで、 ｎ－７＝±１またはｎ－１３＝±１とおいています。 自分が分からないので、「±」です。素因数分解したとき１×Ｐにしかならないので、 ｎ－７＝１またはｎ－１３＝１とおいてしまいました。 なぜ、±１とおけるのかが分かりません。要は－１がどのようにして条件になるのかが理解 できていません。 そういうわけでございます。考え方の質問です。
- ベストアンサー
- 数学・算数
- C言語で正の整数n を受け取って、この数列の第1 項から第n 項までの
C言語で正の整数n を受け取って、この数列の第1 項から第n 項までのフィボナッチ数列を求めて表示、および結果をファイルに保存するプログラムを作ってみました。 ですが、答えがおかしくなります（具体的にはーがつくものが交互にでてきます）・・・コンパイルはできたのですが・・・ 環境はvisual c++2010expressです。 また、a[ ]の配列をもっと増やす方法はないでしょうか・・・大きな値を指定してやると、プログラムを実行したら「このプログラムは停止しました～」という画面が出てきます・・・ また、ファイルを保存するときにfprintfで保存しようと思うのですがa+だとうまく保存されるのですがw+だと最後から一つ前のものしか書き込まれません・・・なぜなのでしょうか・・ どなたか教えていただけないでしょうかｍ（ ）ｍ ソースはこちらです #include<stdio.h> int main(void){ int i; int n; int a[9999]; printf("n? "); scanf("%d",&n); while(n<0){ printf("nは0より大きい整数でお願いします\n"); printf("n? "); scanf("%d",&n); } for(i=1;i<=n;i++){ if( i == 1 || i == 2 ){ a[i]=1; } else{ a[i]=a[i-1]+a[i-2]; } } for(i=1;i<=n;i++){ printf("a[%d] = %d\n",i,a[i]); } for (i=1;i<n;i++) { FILE *file; file = fopen("k04a.txt","w+"); fprintf(file,"a[%d] = %d\n",i,a[i]); fclose(file); } return 0; }
- ベストアンサー
- C・C++・C#
- 再帰関数とユークリッドの互除法を用いて最大公約数を求める
学校の課題で、再帰関数とユークリッドの互除法を用いて１０～１０００００までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。 #include <stdio.h> /* 正整数 n, m の最大公約数を計算する */ int gcd(int n, int m) { int res; res = n % m; if (res == 0) return m; /* 最大公約数が求まった */ return gcd(m, res); /* 再帰呼び出し */ } int main(void) { int i,j; for(i=10000;i>=10;i--){ for(j=10;j=10000;j++){ printf("%d to %d no saidaikouyakusuu ha %d \n", i, j, gcd(i, j)); } } return (0); } です。期限が今日の夜までで、ぎりぎりなんですがよろしくお願いします。
- ベストアンサー
- C・C++・C#
- 素因数分解の問題教えて下さい。
ある整数Ｎを素因数分解するとN=2^10×3^15×5^10×7^2となった。 この整数Ｎの正の約数のうち１の位が１であるものは何個あるか求めよ。 という問題をいろいろ考えたり周りの人にも聞いたのですが，どのようにしたらよいかわかりません。 答えは11個らしいのですが、詳しい解説を教えていただけませんか。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素因数プログラムで、間違えて因数4で割らない
練習問題 5-15 2以上の数値を入力し、素因数分解した結果を表示しなさい。 疑問ですが、素因数分解なので割る数字は、２．３．５．７．・・・の自分の数字しか割りきれない数字で 割ります。それでは、以下のプログラムはどこでそれを判断しているのでしょか？ ４で割ろうとしないのは、どこのプログラムが司っているのでしょうか もし！見えない取り組みがあれば宜しくお願いします。 以下プログラムです。 1) int n, x; 2) scanf("%d", &n ); 3) for( x = 2 ; n > 1 ; x++ ){ 4) while( ( n % x ) == 0 ){ 5) printf( "%d ", x ); 6) n /= x; } }
- ベストアンサー
- C・C++・C#
- 素因数分解のプログラムを作成しました。
素因数分解のプログラムを作成しました。 なぜか11桁を超えた場合、正しく表示されません！！ アドバイス等お願いします。 あと、処理時間も組んでみましたがこちらもうまくいきません。 改善をお願いしますm(_ _)m #include<stdio.h> #include<time.h> void fanction(int); void main(void) { int n; clock_t start_time, end_time; printf("整数を入力してください。\n"); scanf("%d",&n); start_time = clock(); fanction(n); end_time = clock(); printf("\n\n処理時間：%.3f秒\n",(double)(end_time - start_time) / CLOCKS_PER_SEC); return 0; } void fanction(int n) { int m; char c='='; for(m=2;n != 1;m++) { while(n%m == 0) { n = n/m; printf("%c%d",c,m); c='*'; } } }
- 締切済み
- C・C++・C#
