【プログラミング】

Nという数字の入力に対して、{N-1, N-2, N-3, ..... 1}の最小公倍数を求めるプログラミングを作成してください。
言語はCかPHPでお願いします。

(例)
入力:6 ( {5, 4, 3, 2, 1}の最小公倍数 )
出力:60

回答の条件
  • 1人1回まで
  • 登録:2008/08/20 19:53:21
  • 終了:2008/08/20 21:01:17

ベストアンサー

id:pahoo No.1

pahoo回答回数5960ベストアンサー獲得回数6332008/08/20 20:56:01

ポイント60pt

PHPで書いてみました。

力任せですが、hoge が目的の値を求める関数です。

引数のエラーチェックは一切行っていませんのでご注意を。

//最大公約数
function gcd($x, $y) {
    if ($y == 0)    return $x;
    else            return gcd($y, $x % $y);
}

//最小公倍数
function lcm($x, $y) {
    return $x * $y / gcd($x, $y);
}

//目的の関数
function hoge($n) {
    $y = $n;
    for ($m = 1; $m < $n; $m++) {
         $y = lcm($y, $m);
    }
    return $y;
}
id:fashion0208

有り難うございました。:)

2008/08/20 21:00:45
  • id:dev_zer0
    ちなみにC版、引数に数値を与えると結果が出力される
     
    #include <stdio.h>
     
    int f(int n);
    int lcm(int m, int n);
    int gcd(int m, int n);

    int main(int argc, char *argv[]) {
      int n;
     
      /* パラメータチェック */
      if(argc != 2 || ((n = atoi(argv[1])) <= 0)) {
        fprintf(stderr, "usage:%s number\n", argv[0]);
        exit(1);
      }
     
      printf("ret:%d\n", f(n-1));
      return 0;
    }
     
    /* この関数でハマった */
    int f(int n)
    {
      int i, t = n;
      for (i = 1; i < n; i++) {
        t = lcm(t, i);
      }
      return t;
    }
     
    /* 最小公倍数を求める */
    int lcm(int m, int n)
    {
      return m * n / gcd(m, n);
    }
     
    /* 最小公倍数を求める(ユークリッドの互除法) */
    int gcd(int m, int n)
    {
      if (n == 0) return m;
      return gcd(n, m % n);
    }
     
    f()関数の実装に悩んでたら先を越されてしまった...
  • id:fashion0208
    fashion0208 2008/08/20 23:12:04
    >dev_zer0さん
    有り難うございます。m(_ _)m
    こんなに短時間に解いていただけるとは思っていなかったので、大変有り難いです。:)
  • id:upu
    これらのプログラムは
    nと2の最小公倍数を求める
    求められた物と次の数の最小公倍数を求める
    をすべての数でやった物を表示する力任せの方法です

    数学的な知識を使って,効率を上げることができそうです.

    最小公倍数ですが,
    それぞれの数(n-1,n-2,...,1)を素因数分解したときに現れる
    それぞれの素因数における,最大の指数を調べ
    すべての素因数の指数が調べた値の最大である数が,最小公倍数となる


    2^3*3^2*7^1=336
    2^1*3^3*5^2=1350
    5^1*7^2*9^1=2205
    この3つの数の最小公倍数は
    2^3*3^3*5^2*7^2*9^1=2381400となる
    (2の指数の最大値は336の3
     3の指数の最大値は1350の3
     5の指数の最大値は1350の2
    7の指数、9の指数の最大値は1)
  • id:upu
    そこで、
    n-1,n-2,...,1
    これらの数をそれぞれ因数分解したときに発見される
    それぞれの素数の指数の最大値を見つける方法ですが

    たとえば、素数2の指数の場合ですが
    純粋に、2のX乗がN未満かを調べる事で確認できます。

    たとえば、
    N=2000の時、1~1999を素因数分解したときにあらわれる
    2の指数の最大値ですが
    2^10=1024で、10は含まれて、2^11=2048で11は含まれないので
    2の指数の最大値は10であることがわかります
    同様に
    3^6=729で、3^7=2187なので、3の指数の最大値は6であることがわかります
    同様に、1999までに現れるすべての素数について
    指数の最大値を計算し
    2^10*3^6*5^A*7^B*...
    としていけば、最小公倍数を求めることができるはずです
  • id:upu
    とりあえず、とっさに思いついた方法だけで^^;

    int fanc(int n){
    int result=1;
    int t;

    //n-1までの素数列を得る(中身は略)
    list sosu = get_sosu(n-1);

    while(sosu->next != NULL){
    sosu=sosu->next;
    t = sosu->val;
    while(t < n){
    result *= sosu->val;
    t *= sosu->val;
    }
    }
    return result;
    }
  • id:dev_zer0
    > 素因数分解
    ここで質問してよいのかどうか不明なのですが、
    私の知っている限り、「簡単に」素因数分解できるアルゴリズム、
    「簡単に」ある数値が素数であるかを判定するアルゴリズムは無いはずです
    もし存在するならば、現在の暗号化技術が根底から覆されます
    # 今の暗号化技術は大きな数の素因数分解や素数判定は
    # 簡単に求めることが出来ないことを前提とされています
     
    多分、素数を求める最も素朴なアルゴリズムは
    「エラトステネスのふるい」ですけど、
    その場合も力任せで素数を抽出していて、
    それだけで私が書いたCソースに匹敵する量があるはずです
     
    どちらがよりエレガントなんでしょうか?
    # 素数判定してくれる標準関数がある言語があればいいんですが
    # C, PHP共にそんな標準関数は無いはずです
  • id:upu
    >dev_zer0さん

    >素因数分解
    確かに、「大きな数」を「簡単に」素数かどうかを判定するのは難しいというのはよく聞きますが、
    「大きな数」というのは、何十桁もある数であって、
    そのような数になった場合、扱う数も巨大になり、
    すべての数での最小公倍数を一つ一つ計算していくのもまた大きな手間になります

    (ちなみにプログラム中では素因数分解はしません)

    素数列抽出は、私は「エラトステネスのふるい」のアルゴリズムぐらいしか知りませんが
    最小公倍数や最大公倍数を求めるアルゴリズムよりはソース量があったはずです
    ソース量は多くなりますが、効率よく計算できるかもと思って提案してみました

    計算量の計算は苦手で、客観的判断はできないのですが・・・^^;

    >標準関数
    標準関数があったとしても、その関数が多くの計算をするはずなので
    ソースは短くなったとしても、計算量は減らなさそうです
  • id:fashion0208
    fashion0208 2008/08/21 13:18:46
    >dev_zer0さん、upuさん
    色々と有り難うございます。

    現状、入力値Nが100未満ということが分かっているので、
    リスト化したりして使うことにしました ^^;

    確かに数字が10万とか100万になると計算がしんどくなりそうですね。。。
  • id:dev_zer0
    > upuさん
    なるほど、計算量として考えると合理的かもしれません
    入力値が100未満という前提ならば、提示してもらったプログラム中の
    list sosuの中に予め100未満の素数を突っ込んでおくとかすると
    かなりエレガントなプログラムになりそうですね

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません