C言語でProject Euler(プロジェクト・オイラー)に挑戦 > スポンサー広告 > アルゴリズムを考える【素数】

    C言語でProject Euler(プロジェクト・オイラー)に挑戦 > アルゴリズムいろいろ > アルゴリズムを考える【素数】

    スポンサー広告

    スポンサーサイト

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

    アルゴリズムいろいろ

    アルゴリズムを考える【素数】

    Project Euler(プロジェクトオイラー)の問題を解いていくにあたり、数学的知識が必要だということがわかってきました。

    C言語Project Euler(プロジェクトオイラー)の問題を解くためには、アルゴリズムがわからないとダメですもんね。

    Project Euler(プロジェクトオイラー)の問題ででてきた
    素数
    のアルゴリズムを考えます。

    この考え方がわかれば、C言語に限らずどんな言語でも解くことができると思います。


    素数とは

    1 より大きな正の整数 n が 1 と n 自身以外に約数をもたないとき n は素数であるという。

    <<例>>
    ● 3 は 1 と 3 以外に約数を持たないので、素数である。
    ● 4 は 1 と 4 以外に 2 を約数に持つので、素数ではない。

    <<素数の求め方>>
    ● その1
    1 とその数 n 以外のすべての数で割る。

    103が素数かどうか調べる場合、
    103/2、103/3、103/4、・・・ 103/101、103/102
    この中で、割り切れるものがあれば、103は素数ではないと言える。

    ● その2
    その数 n の正の平方根を超えない最大の素数までのすべての数で割る。

    103が素数かどうか調べる場合、
    √103は約10なので、103を2,3,5,7の4つの素数で割ってみる。

    ● その3
    エラトステネスのふるい を使う。

    素数を求める方法として,古来有名なものに「エラトステネスのふるい」があります。
    (エラトステネスはギリシア時代の人の名前だそうです)

    その方法は、
     1 は素数とはしないので除外する。
     2 を残して 2 で割り切れるものを除外する。
     3 を残して 3 で割り切れるものを除外する。
     ( 4 は除外されている。)
     5 を残して 5 で割り切れるものを除外する。
     ( 6 は除外されている。)
     7 を残して 7 で割り切れるものを除外する・・・・・
    のように進めていき、残った数が素数と考える。


    他にも素数の求め方はあると思います。
    プログラミングするのに「知っておいたほうがいいよ!!」と言う素数の求め方がありましたら、ぜひ教えてください



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



    <<C言語でProject Euler 【Problem7】C言語でProject Euler(プロジェクト・オイラー)に挑戦C言語の記述について【¥(円マーク)と \ (バックスラッシュ)】>>

    <<C言語でProject Euler 【Problem7】C言語でProject Euler(プロジェクト・オイラー)に挑戦C言語の記述について【¥(円マーク)と \ (バックスラッシュ)】>>

    コメント

    コメントする

    トラックバック


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

    カテゴリ

    最新記事

    WiMAX & WiFi & モバイル

    便利ソフトいろいろ

    最新トラックバック

    最新コメント

    カウンター

    BlogRancking



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