C言語関係掲示板

過去ログ

No.607.3個以上の数の最大公約数

[戻る] [ホームページ]
No.5834

3個以上の数の最大公約数
投稿者---kon(2003/04/16 22:28:57)


2個の自然数の最大個約数は
ユークリッドの互除法で求められたのですが、
3個以上になるとどうすればいいのかわからなくなりました
お願いします。

No.5836

Re:3個以上の数の最大公約数
投稿者---aki(2003/04/17 00:33:10)


2個の自然数の最大公約数を求める関数を int gcm2(int, int); とすると、3個の場合は、

int gcm3(int a, int b, int c)
{
    return gcm2(gcm2(a, b), c);
}

4個、5個の場合は、

int gcm4(int a, int b, int c, int d)
{
    return gcm2(gcm3(a, b, c), d);
}

int gcm5(int a, int b, int c, int d, int e)
{
    return gcm2(gcm4(a, b, c, d), e);
}

一般化すると、

#include <stdarg.h>

int gcmn(int n, ...)
{
    va_list ap;
    int i, x;

    va_start(ap, n);
    x = va_arg(ap, int);
    for (i = 0; i < n - 1; i++)
        x = gcm2(x, va_arg(ap, int));
    va_end(ap);
    return x;
}


No.5837

Re:3個以上の数の最大公約数
投稿者---kikk(2003/04/17 00:40:09)


ども。


1例を。ほかにもあると思います。
公約数の約数は公約数であることがポイント。

1. n個の自然数の集合から任意の2つを取り出す。
2. その2つの最大公約数を求める。
3. 2.の結果をもとの集合に戻す。 -> 集合の要素数はn-1個になる
4. 自然数の集合の要素数が1になるまで1.から繰り返す。
※ 2.で、最大公約数が1だったら即座に終了してもOK

"集合"は配列で実現するとよろしいかと。


では。