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

    スポンサー広告

    スポンサーサイト

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

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

    C言語でProject Euler 【Problem10】

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


    /* Problem 10 †*/
    10以下の素数の和は 2+3+5+7=17 である。
    200万以下の全ての素数の和を計算しなさい。


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

    int main(void)
    {
        int i=2, j, flg;
        double ans=0;

        while(i <= 2000000){
            flg=0;

            for(j=2; j<=(int)sqrt(i); j++){
                if(i%j == 0){
                    flg = 1;
                    break;
                }
            }

            if(flg==0){
                ans += i;
            }

            i++;
        }

        printf("%.lf\n", ans);

        getch();
        return 0;
    }


    でた素数
    C言語でProject Euler 【Problem7】と同じやり方で素数を求めました。
    Problem7のときは、時間が気にならなかったけど、200万以下となると・・・
    数秒待たないとダメです。
    正直、気になるくらいの時間です

    はじめはアルゴリズムを考える【素数】の「その1」でやってみました。
    とても時間がかかり、まったく使い物なりません。
    「その2」に変えてみましたが、それでもまだ時間がかかる。
    これこそ、「エラトステネスのふるい」を使うときなのでしょうか・・・
    わかっていてもちょっと逃げてしまいます

    Project Euler(プロジェクトオイラー)を続けるためには、まず素数の求め方「エラトステネスのふるい」を会得する必要があるのかも。
    Project Euler(プロジェクトオイラー) problem10、も「エラトステネスのふるい」を使えば速くなるのかどうかは、まだ試していません。
    できたらまた報告します!

    C言語だから遅い、とかそういうのはないと思うので、やっぱりアルゴリズムの問題ですよね




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


    スポンサーサイト

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

    C言語でProject Euler 【Problem9】

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


    /* Problem 9 †*/
    ピタゴラスの三つ組(ピタゴラスの定理を満たす自然数)とは a < b < c で
    a^2 + b^2 = c^2
    を満たす数の組である。
    例えば、3^2 + 4^2 = 9 + 16 = 25 = 5^5
    a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する。
    この a, b, c の積を計算しなさい。

    ※ ^ はべき乗を表しています。


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

    int main(void)
    {
        int a, b, c, ans;

        for(a=1; a<(1000/3); a++){

            for(b=a; b<(1000/2); b++){
                c = 1000 - a - b;

                if(a*a + b*b == c*c){
                    printf("%d, %d, %d %d\n", a, b, c, a*b*c);
                    return 0;
                }

            }
        }

        getch();
        return 0;
    }



    Project Euler(プロジェクトオイラー) Problem9、これは a, b, c それぞれの数をどう置くか、ですよね。

    a を 1 から 1000/3 までの数字とした場合、
    b は a から 1000/2 までの数字。
    c は 1000-a-b となる。

    他にはどういう考え方があるのでしょうか


    ちょっと関係ないのですが・・・
    こういうサイトで a の 2 乗を表したいときの表記は、
    a^2 でいいのでしょうか



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


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

    C言語でProject Euler 【Problem8】

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


    /* Problem 8 †*/
    以下の1000桁の数字から5つの連続する数字を取り出してその積を計算する。
    そのような積の中で最大のものの値はいくらか。


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

    int main(void)
    {
        char str[]="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

        char str2[1];
        int i, j, k, buf[5], ans, ansmax = 0;

        for(i=0; i<=1000-5; i++){
            k = 4;

            for(j=i; j<=i+4; j++){
                // 整数型配列にセットするため、1文字にしてから数値に変換
                str2[0] = str[j];
                buf[k] = atoi(str2);

                k--;
            }

            ans = 1;
            for(j=0; j<5; j++) ans *= buf[j];
            if(ansmax < ans) ansmax = ans;

        }

        printf("最大値 %d\n", ansmax);

        getch();
        return 0;
    }




    このProject Euler(プロジェクトオイラー) Problem8、私には難関でした。
    C言語の配列とか数値から文字列への変換とかを、わかっていないんだな、と痛感
    でも、この問題が解けて、少しだけわかったような気がします




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


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

    C言語でProject Euler 【Problem7】

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


    /* Problem 7 †*/
    素数を小さい方から 6 つ並べると、2, 3, 5, 7, 11, 13 であり、
    6 番目の素数は 13 である。
    10001 番目の素数を 求めよ。


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

    int main(void)
    {
        int i, j, cnt;
        int flg;

        cnt = 1;
        i = 2;

        while(cnt <= 10001){
            flg=0;

            for(j=2; j<=(int)sqrt(i); j++){
                if(i%j == 0){
                    flg = 1;
                    break;
                }
            }

            if(flg==0){
                cnt++;
            }

            i++;
        }

        printf("%d\n", i-1);

        getch();
        return 0;
    }


    この問題は、「素数」の求め方がポイントなんだと思います。
    Project Euler(プロジェクトオイラー)、数学の知識も必要とします。

    アルゴリズムを考える【素数】
    の中の「その2」を使った方法でやってみました。
    本来は、平方根を超えない最大の素数で割るのですが、
    今回やった方法は
    平方根を超えない数で割る、と言ったものです。

    もっと数が大きくなってきたら今回のやり方ではダメなんだと思います。
    が・・・
    この問題なら時間もそうかからないようなので、単純な考え方でやってしまいました

    やっぱりこういう問題も「エラトステネスのふるい」を使うべきなのでしょうか
    正しいというか、こうするべき!なようなもの、ありましたらぜひとも教えてください




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


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

    C言語でProject Euler 【Problem6】

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


    /* Problem 6 †*/
    最初の10個の自然数について、その和の二乗と、二乗数の和は以下の通り。
    1^2 + 2^2 + ・・・・・ + 10^2 = 385
    (1 + 2 + ・・・・・ + 10)^2 = 3025
    これらの数の差は 3025 - 385 = 2640 となる。
    同様にして、最初の100個の自然数について和の二乗と二乗の和の差を求めよ。


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

    int main(void)
    {
        int i;
        int sum1=0, sum2=0;

        for(i=1; i<=100; i++){
            sum1 += i*i;
            sum2 += i;
        }

        sum2 *= sum2;

        printf("%d\n", sum2-sum1);

        getch();
        return 0;
    }


    この問題は、単純にこれでいいんだよねぇ。
    Project Euler(プロジェクトオイラー)は問題の順番と難易度は関係ないようです。
    まぁ、難しいと思うっていうのには個人差がありますが



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


    カテゴリ

    最新記事

    WiMAX & WiFi & モバイル

    便利ソフトいろいろ

    最新トラックバック

    最新コメント

    カウンター

    BlogRancking



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