C言語関係掲示板

過去ログ

No.1286 約数の和を求めるプログラム

[戻る] [ホームページ]
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として、
  1. k=0;
  2. n==1まで以下を繰り返す
  3. for(m=2;n%m;m++);
  4. n/=m;
  5. k+=m

とすると、あえて素数を求める必要がないので、簡単かもしれません。




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;
>の行なんですがここはどういう処理なんでしょうか?

  • 二つのunsigned型の変数nとmを宣言かつ定義しています。
  • 変数nを2004に初期化しています。




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の公式を使うと、速くなりそうな気がします。

#私はもうすぐ三年になりますが、初めて半年の頃は...覚えていませんね。
#以上、追加です。