C言語でProject Euler(プロジェクト・オイラー)に挑戦 > スポンサー広告 > C言語でProject Euler 【Problem5】

    C言語でProject Euler(プロジェクト・オイラー)に挑戦 > Project Euler(プロジェクト・オイラー)【Problem 1~P5】 > C言語でProject Euler 【Problem5】

    スポンサー広告

    スポンサーサイト

    上記の広告は1ヶ月以上更新のないブログに表示されています。
    新しい記事を書く事で広告が消せます。

    Project Euler(プロジェクト・オイラー)【Problem 1~P5】

    C言語でProject Euler 【Problem5】

    Project Euler(プロジェクトオイラー)のproblem5☆
    C言語を使っています。


    /* Problem 5 †*/
    2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。
    では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。


    #include <stdio.h>
    #include <conio.h>

    int main(void)
    {
        int i, num, flg;

        num=20;
        while(1){

            flg = 0;
            for(i=2; i<=20; i++){
                if(num%i != 0){
                    flg = 1;
                    break;
                }
            }

            if(flg == 0) break;
            num++;
        }

        printf("%d\n", num);

        getch();
        return 0;
    }


    そのまま素直に問題を解くだけなら、Project Euler(プロジェクトオイラー)の初めの方の問題の中でも難易度としてはそんなに高くないと思うのですが・・・
    ただ、このやり方だと、時間がちょっとかかるんですよね
    待てない程の時間ではないので、これでヨシとしておこう。

    C言語にかぎらず、どの言語でやったとしても、アルゴリズムを考えなおさないと、やっぱり処理は遅いんだろうな。
    いい方法があれば、教えてください



    ☆応援お願いします☆
    にほんブログ村 IT技術ブログ C/C++へ
    にほんブログ村


    <<基本情報技術者試験 申し込みました!C言語でProject Euler(プロジェクト・オイラー)に挑戦C言語でProject Euler 【Problem4】>>

    <<基本情報技術者試験 申し込みました!C言語でProject Euler(プロジェクト・オイラー)に挑戦C言語でProject Euler 【Problem4】>>

    コメント

    • No title
    • 1.ツムジ
    • 2011年02月26日 |
    • この問題は、「1 〜 20 の整数すべての最小公倍数を求める」ということになります。

      整数 a, b の最大公約数を gcd(a, b)、最小公倍数を lcm(a, b) とすると、
      lcm(a, b) = a * b / gcd(a, b)

      という関係になっています。

      また、最小公倍数は「ユークリッドの互除法」というアルゴリズムで間単に計算できます。

      #include <stdio.h>


      /* 最大公約数を求める(ユークリッドの互除法) */
      int gcd (int a, int b)
      {
      int tmp = 0;

      while (b > 0) {
      tmp = b;
      b = a % b;
      a = tmp;
      }
      return (a);
      }

      /* 最小公倍数を求める */
      int lcm (int a, int b)
      {
      return (a / gcd(a, b) * b);
      }


      int main(void)
      {
      int ans = 1;
      int i;

      for (i = 2; i <= 20; i++) {
      ans = lcm(ans, i);
      }

      printf ("%d\n", ans);
      return (0);
      }

      約10年ぶりに C のコードを書いたので、おかしいところがあるかもしれませんが……。
    • [編集]
    • ツムジさん!ありがとうございます
    • 2.CEuler
    • 2011年02月27日 |
    • なるほど。。
      ふむふむ、見れば見るほどなるほどです。
      また自分で噛みしめて組みなおしてみます。

      また是非ともご指導のほど、よろしくお願いします☆
      ありがとうございました♪
    • [編集]
    • とおりすがり
    • 3.ダメ子
    • 2011年03月01日 |
    • 1から10までを因数分解して
      それぞれの指数の一番多いの
      拾うほうが速いかなと思いました
      1
      2
      3
      4=2^2
      5
      6=2*3
      7
      8=2^3
      9=3^2
      10=2*5
      より最小は
      2^3*3^2*5*7=2520
    • [編集]
    • 管理人のみ閲覧できます
    • 4.
    • 2011年03月01日 |
    • このコメントは管理人のみ閲覧できます
    • [編集]
    • ダメ子さん!ありがとうございます
    • 5.CEuler
    • 2011年03月21日 |
    • お礼が遅くなって申し訳ありません。
      意味はよくわかりました!ありがとうございます。
      また考えてみます。実際にできるかどうかはわかりませんが・・・

      また教えてください♪
      ありがとうございました。
    • [編集]
    • Re: すいません
    • 6.CEuler
    • 2011年03月21日 |
    • ツムジさん、わざわざありがとうございます。
      私にはとても役に立つ内容でしたので、削除はひかえさせていただきますね。
      またお願いします☆
    • [編集]

    コメントする

    トラックバック


    この記事にトラックバックする(FC2ブログユーザー)

    カテゴリ

    最新記事

    WiMAX & WiFi & モバイル

    便利ソフトいろいろ

    最新トラックバック

    最新コメント

    カウンター

    BlogRancking



    上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。