No.17028![]() |
約数の和を求めるプログラム 投稿者---かなみ(2004/10/03 16:51:32) |
||
はじめまして。質問なのですが、自然数nをキーボードから入力して、その約数の和を求めるプログラムを作りたいのですが、どなたか教えてください。よろしくお願いします。 |
No.17029![]() |
Re:約数の和を求めるプログラム 投稿者---RAPT(2004/10/03 17:01:06) |
||
1.その数の約数を求める 2.1で求めた値の合計を算出する |
No.17030![]() |
Re:約数の和を求めるプログラム 投稿者---YuO(2004/10/03 17:05:12) |
||
>はじめまして。質問なのですが、自然数nをキーボードから入力して、その約数の和を求めるプログラムを作りたいのですが、どなたか教えてください。よろしくお願いします。 どれが「質問」なのですか? 質問の本文が見つからないのですが……。 |
No.17037![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/03 20:24:34) |
||
プログラムにするのは、面倒くさそうなのでお任せします。 素因数分解し各数が何回あったかカウントしておく。 50 を例にすると、 2^1*5^2 この各素数の、0乗からn乗までの各パターンを すべて合計する。 2^0*5^0 = 1 2^1*5^0 = 2 2^0*5^1 = 5 2^1*5^1 =10 2^0*5^2 =25 2^1*5^2 =50 合計93かな・・ for ループじゃ難しそうだから、再帰かな・・・ |
No.17038![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy(2004/10/03 21:33:32) |
||
>素因数分解し各数が何回あったかカウントしておく。 元の数をnとして、
とすると、あえて素数を求める必要がないので、簡単かもしれません。 |
No.17039![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy(2004/10/03 21:57:11) |
||
プログラムにすると、こんな感じです。 #include <stdio.h> int main(void) { unsigned n=2004,m; while(n>1) { for(m=2;n%m;m++); n/=m; printf("%d\n",m); } return 0; } |
No.17086![]() |
Re:約数の和を求めるプログラム 投稿者---かなみ(2004/10/05 00:19:22) |
||
#include <stdio.h> int main(void) { unsigned n=2004,m; while(n>1) { for(m=2;n%m;m++); n/=m; printf("%d\n",m); } return 0; } この中の unsigned n=2004,m; の行なんですがここはどういう処理なんでしょうか? |
No.17087![]() |
Re:約数の和を求めるプログラム 投稿者---YuO(2004/10/05 00:33:45) |
||
>この中の unsigned n=2004,m; >の行なんですがここはどういう処理なんでしょうか?
|
No.17106![]() |
Re:約数の和を求めるプログラム 投稿者---かなみ(2004/10/05 20:22:04) |
||
#include <stdio.h> int main(void) { unsigned n=2004,m; while(n>1) { for(m=2;n%m;m++); n/=m; printf("%d\n",m); } return 0; } このプログラムは実行してもうまくいきません。 もう一つのほうは正しく動きます。 |
No.17108![]() |
Re:約数の和を求めるプログラム 投稿者---REE(2004/10/05 20:33:53) |
||
>#include <stdio.h> > >int main(void) >{ > unsigned n=2004,m; > while(n>1) { > for(m=2;n%m;m++); > n/=m; > printf("%d\n",m); > } > return 0; >} > >このプログラムは実行してもうまくいきません。 >もう一つのほうは正しく動きます。 このプログラムって・・素因数分解? |
No.17109![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy(2004/10/05 21:02:02) |
||
>このプログラムって・・素因数分解? 見た飯です。 |
No.17044![]() |
Re:約数の和を求めるプログラム 投稿者---かずま(2004/10/04 02:26:09) |
||
> for ループじゃ難しそうだから、再帰かな・・・ for ループだと、どこが難しいのでしょうか? #include <stdio.h> int main(void) { int n, i, s; while (scanf("%d", &n) == 1 && n > 0) { printf(" 1"), s = 1; for (i = 2; i <= n; i++) if (n % i == 0) printf(" + %d", i), s += i; printf(" = %d\n", s); } return 0; } |
No.17061![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/04 12:45:26) |
||
その方法、時間がかかりそうだったので避けたのですが・・・ 今時のコンピュータの速度だったら、 あまり問題にならないかもしれませんね。 それだったら、forループで十分です。 |
No.17110![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy(2004/10/05 21:05:08) |
||
>その方法、時間がかかりそうだったので避けたのですが・・・ 公開鍵暗号方式の一種のRSAは、それを利用していると言えます。 素因数の和を簡単に求められる公式でもあれば、話は別でしょうが。 |
No.17112![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/06 01:26:26) |
||
>公開鍵暗号方式の一種のRSAは、それを利用していると言えます。 それが何かはよくわからなかったけど 無理矢理作ってみました(^^; #include <stdio.h> #include <stdlib.h> typedef struct List{ unsigned no,count; struct List *next; } List; List *mkList(unsigned data) { static List end = {0,0,NULL}; List *retptr = &end; unsigned no = 2; for (;no*no <= data;no++) { if (retptr->count != 0) { List *last = malloc (sizeof (List)); last->count = 0; last->next = retptr; retptr = last; } retptr->no = no; while (data%no == 0) { retptr->count++; data/=no; printf(" %u ",no); } } if (data != 1) { List *last = malloc (sizeof (List)); last->count = 1; last->no = data; last->next = retptr; retptr = last; printf("%u",data); } return retptr; } void printList(List *list) { printf("\n"); while (list) { printf("%u * %u\n",list->no,list->count); list = list->next; } } unsigned answer(List *list,unsigned no) { unsigned ret = 0; unsigned count; for (count = 0;count<=list->count;no *= list->no,++count) { if (list->next) ret += answer(list->next,no); else ret += no; } return ret; } int main() { unsigned indata; List *start; printf("Input Data:"); scanf("%u",&indata); printf("%u の分解は、\n",indata); start = mkList(indata); printList(start); printf("答えは:%u\n",answer(start,1)); return 0; } かなり手抜きです。 しかし・・・汚いソース |
No.17113![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/06 09:25:31) |
||
あまりに醜かったので 一部書き換えました。 List *ListAlloc(List *next) { List *retptr = malloc(sizeof (List)); if (!retptr) { fprintf(stderr,"malloc error!!\n"); exit(1); } retptr->no = retptr->count = 0; retptr->next = next; return retptr; } List *mkList(unsigned data) { unsigned no = 2; List *retptr = ListAlloc(NULL); retptr->no = no; while (data % no == 0) { retptr->count++; data/=no; } for (no++;no*no <= data;no+=2) { if (retptr->count) retptr = ListAlloc(retptr); retptr->no = no; while (data % no == 0) { retptr->count++; data /= no; } } if (data != 1) { if (retptr->count) retptr = ListAlloc(retptr); retptr->no = data; retptr->count = 1; } return retptr; } こんなもんかな?? |
No.17114![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy変化前(2004/10/06 13:00:18) |
||
それで早くなるのですか?何度もmallocが呼ばれているに、一度もfreeが呼ばれていないというのも気になりますが。 |
No.17117![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/06 14:01:12) |
||
>それで早くなるのですか?何度もmallocが呼ばれているに、一度もfreeが呼ばれていないというのも気になりますが。 一応、数がでかくなったときには早いはずです。 (バグってなければ(^^;) 1000000000くらいで比較してもらうとわかるかな? (unsigned が 32bit であることを想定してますが。) あまり大きすぎると、オーバーフローします。 そこまでのチェックは省略してますので。 小さい数なら、17044 の方が早いかもしれないですが、 そこまで検証してません。 free してないのが気になるなら、その処理を追加すればいいだけでは? main() を抜けたら処理系が勝手に free するはずなので、 追加するつもりがなかったので、省略しましたが、 繰り返し使用するなら有った方がいいと思います。 printListの様に順次追っかけて、freeすればいいだけなので。 mkList -> 素数に分解する。 チェックは sqrt(data) まで(n*nでチェック) 割り切れなければ、それは素数であるから、素数リストに追加 変更の物は、2 の後、3,5,7,9 など奇数のみチェック。 answer -> 各素数の要素パターンを全て加算。 全て、最初に書いた仕様通りです。 |
No.17118![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy変化前(2004/10/06 14:30:02) |
||
>一応、数がでかくなったときには早いはずです。 元の数よりも、素因数の大きさに依存するでしょう。 しかしながら、繰り返しで時間を計ると、前に書いたプログラムの方が速いです。 mallocの繰り返しによって、速度が低下するからでしょうか。 ところで、答えの数字は何を意味しているのですか? |
No.17119![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/06 14:40:53) |
||
>元の数よりも、素因数の大きさに依存するでしょう。 17044 は、1から元の数まで割る数をループさせているから 元の数に影響されやすいと思うのですが。 >しかしながら、繰り返しで時間を計ると、前に書いたプログラムの方が速いです。 >mallocの繰り返しによって、速度が低下するからでしょうか。 小さい数なら前の方が早いでしょう。 大きい数だった場合・・・・わかりません。 >ところで、答えの数字は何を意味しているのですか? 約数の和を求めるプログラムではなかったでしょうか?? |
No.17121![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy変化前(2004/10/06 14:45:51) |
||
>>ところで、答えの数字は何を意味しているのですか? >約数の和を求めるプログラムではなかったでしょうか?? 10の約数の和が18になるのですか? |
No.17124![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/06 15:00:35) |
||
>10の約数の和が18になるのですか? 17044 を実行してもらえればわかりますが、 18 になります。 1 と、10 も、約数です。 |
No.17127![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy変化前(2004/10/06 15:13:42) |
||
>1 と、10 も、約数です。 OTL 素因数に限定なんてしていませんでしたね。 |
No.17125![]() |
Re:約数の和を求めるプログラム 投稿者---かずま(2004/10/06 15:10:50) |
||
> こんなもんかな?? 素因数分解のプログラムを C++ で書いてみたら、次のようになりました。 #include <iostream> #include <map> using namespace std; struct S { map<int, int> a; int sum; }; void func2(S &s, map<int, int>::iterator p, int d) { if (p == s.a.end()) { s.sum += d; cout << (d==1 ? " " : " + ") << d; } else { int n = p->second, v = p->first, k = 1, i = 0; for (++p; i <= n; i++, k *= v) func2(s, p, d * k); } } void func(int n) { S s; int i = 2; while (i <= n) if (n % i) i++; else n /= i, s.a[i]++; map<int, int>::iterator p = s.a.begin(); cout << " = " << p->first << "^" << p->second; if (p != s.a.end()) while (++p != s.a.end()) cout << " * " << p->first << "^" << p->second; cout << endl; s.sum = 0; func2(s, s.a.begin(), 1); cout << " = " << s.sum << endl; } int main() { int n; while (cin >> n) func(n); } |
No.17128![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/06 15:19:03) |
||
>素因数分解のプログラムを C++ で書いてみたら、次のようになりました。 C++ は知らないの・・・しくしく |
No.17126![]() |
Re:約数の和を求めるプログラム 投稿者---たいちう(2004/10/06 15:11:22) |
||
>素因数の和を簡単に求められる公式でもあれば、話は別でしょうが。 素因数分解ができた後なら約数の和の公式があることはあります。 50 = 2^1 * 5^2 から、約数の和は (1 + 2) * (1 + 5 + 25) = 93 p1^n1 + p2^n2 + ... について、 (p1^(n1 + 1) - 1) / (p1 - 1) * (p2^(n2 + 1) - 1) / (p2 - 1) * ... となります。 この公式で速くなるとは限りませんが。それとちゃんと見てないのですが、 既に誰かのソースがこの公式を利用していたら御免なさい。 |
No.17129![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/06 15:20:10) |
||
まだ誰も書いてないと思います。 そういうので出るんだ・・・知らなかった。 |
No.17134![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy変化前(2004/10/06 16:00:17) |
||
#高校でやりましたね。 使ってみましたが、どうですか? #include <stdio.h> unsigned pw(unsigned x,unsigned y) { unsigned i,r; for(i=0,r=1;i<y;i++) r*=x; return r; } int main(void) { unsigned n,m=0,k=1,r,l,pm=3; printf("n="); scanf("%d",&n); for(r=1;n>1&&n%2==0;r++) n/=2; l=1; while(--r) l+=pw(2,r); k*=l; for(r=1;n>1;) { for(m=pm;n%m;m+=2); if(m==pm) r++; else { l=1; while(--r) l+=pw(pm,r); k*=l; pm=m; r=2; } n/=m; } l=1; while(--r) l+=pw(m,r); k*=l; printf("k=%d\n",k); return 0; } |
No.17136![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/06 16:22:04) |
||
>#高校でやりましたね。 教科書見てみたけど、やってないな・・・ やはり、数一までじゃ世間に通用しないのか・・・ |
No.17146![]() |
Re:約数の和を求めるプログラム 投稿者---かずま(2004/10/06 19:58:18) |
||
> 素因数分解ができた後なら約数の和の公式があることはあります。 その公式を使ってみました。 ただし、割り算は遅いと思われるので、最初の和積の方にしてみました。 #include <stdio.h> int main(void) { int n; while (scanf("%d", &n) == 1) { int i = 2, c = 0, s = 1, k = 1, p = 1; while (i <= n) if (n % i) { if (c) p *= s; i++, c = 0, s = k = 1; } else c++, k *= i, s += k, n /= i; if (c) p *= s; printf(" %d\n", p); } return 0; } |
No.17148![]() |
Re:約数の和を求めるプログラム 投稿者---かずま(2004/10/06 20:25:07) |
||
> if (c) p *= s; > i++, c = 0, s = k = 1; を if (c) p *= s, c = 0, s = k = 1; i++; に訂正します。 |
No.17151![]() |
Re:約数の和を求めるプログラム 投稿者---hermit(2004/10/06 22:15:42) |
||
やっと理解できた。 (1+p1+p1^2+....p1^e1)(1+p2+p2^2+......p2^e2)(........... これで全ての要素の合計が出るんですね。 これなら、値を保持する必要がないから、非常に楽ですね。 |
No.17139![]() |
Re:約数の和を求めるプログラム 投稿者---かなみ(2004/10/06 17:22:59) |
||
みなさんプログラムは得意な方ばかりだと思うのですが、私はまだ初めて半年の初心者です。話の内容がわからないので、ちょっと難しいです・・・ |
No.17141![]() |
Re:約数の和を求めるプログラム 投稿者---たいちう(2004/10/06 17:43:01) |
||
置いてけぼりされてしまっていたんですね。 失礼しました。お詫びに丁寧に説明。 1.キーボードから入力された数字を表示する。 このようなプログラムは作れるでしょうか? できたら次のステップです。 1.キーボードから入力させる(nとする)。 2.1〜nまでを表示する。 6 と入力された場合、 1 2 3 4 5 6 と表示するだけです。 これができたら約数だけ表示しましょう。 (6と入力された場合) 6 % 1 == 0 なので、約数。→表示。 6 % 2 == 0 なので、約数。→表示。 6 % 3 == 0 なので、約数。→表示。 6 % 4 == 0 なので、約数でない。 6 % 5 == 0 なので、約数でない。 6 % 6 == 0 なので、約数。→表示。 結果は 1 2 3 6 と表示されます。 ここまでできたら、1+2+3+6 = 12を計算するだけです。 表示しながら合計を計算しましょう。 途中で行き詰ったらまた質問してください。 |
No.17149![]() |
Re:約数の和を求めるプログラム 投稿者---かなみ(2004/10/06 21:45:29) |
||
詳しい説明ありがとうございます。 ただ、一つだけ 6 % 4 == 0 なので、約数でない。 6 % 5 == 0 なので、約数でない。 のところなんですが、 6 % 4 == 2 なので、約数でない。 6 % 5 == 1 なので、約数でない。 ではないでしょうか?%は割り算の余りだったと思うのですが。間違っていたらごめんなさい。 |
No.17153![]() |
Re:約数の和を求めるプログラム 投稿者---たいちう(2004/10/07 01:21:57) |
||
ごめんなさい。間違っていました。 >6 % 4 == 2 なので、約数でない。 >6 % 5 == 1 なので、約数でない。 これでも正しいのですが、プログラミング的には 6 % 4 != 0 なので、約数でない。 6 % 5 != 0 なので、約数でない。 と、判定してください。 |
No.17143![]() |
Re:約数の和を求めるプログラム 投稿者---Sciggepy変化前(2004/10/06 19:03:09) |
||
とりあえず目的を達成したら、別の方法でやってみるのも悪くありません。 本当に効率がよいかかどうかは判りませんが、17126の公式を使うと、速くなりそうな気がします。 #私はもうすぐ三年になりますが、初めて半年の頃は...覚えていませんね。 #以上、追加です。 |