人生は、日々「わかった!」の積み重ね。成功・成長する方法を研究するブログ。2013.07.26与えられた数字よりも小さい数字の中で素数がいくつあるかを調べるプログラムを作ってくださいふとこんな問題を見つけたので、ビールを飲みながら考えてみました。素数とは、1と自分自身の数字でしか割り切れない正の整数のことです。正の約数の個数が二つの自然数ってことですね。よって、調べる数を、2から順に調べる数-1まで順番に割っていって、すべて割り切れなければ素数。割り切れたら素数ではないので、そこでチェック終了して、次の数へ...。じゅうたん爆撃的に計算すれば数えられます。最初に自力で書いたコードがこちら。'<p>'.$time.'秒掛かりました。</p>';?></body></html>10,000までの数を計算してみたところ、ウチの環境下では計算時間は平均0.80秒でした。一ひねり加えてみた上記のコードは正直に順番に計算しています。・偶数は素数ではない・調べたい数のルートより大きい数で割り切れる数はないなるほど。素数のこれらの性質をコードに組み込んで同じように10,000まで再計算してみました。'<p>'.$time.'秒掛かりました。</p>';?></body></html>計算時間は、平均0.036秒。22倍速くなりました。エラトステネスのふるいもっと素数の高速カウント方法を調べてみると、エラトステネスのふるいという方法があることがわかりました。与えられた数までの倍数をすべて除去して、次の数に進むと、最初に現れる数は必ず素数になります。それをカウントしていきます。diaryさんの記事を参考にコードを書いてみました。'<p>'.$time.'秒掛かりました。</p>';?></body></html>計算時間は0.007秒。プログラム3は、プログラム1より114倍、プログラム2より5倍速くなっています。チェックする数を奇数だけに限定してみました。'<p>'.$time.'秒掛かりました。</p>';?></body></html>計算時間は0.006秒。プログラム1より133倍の速さです。1日で終わる計算が100日かかるもっと大きな数を計算する場合、プログラムの優劣によって、1日で終わる計算が100日かかってしまうこともあるということです。この差は致命的ですよね。私の場合、計算時間が長いプログラムを走らせることはほとんど無いのですが、今後大量のデータを処理する計算コードを書くときは、アルゴリズムを良く考えて、なるべく計算量が減るコードを書くように気をつけたいと思いました。▼▼▼▼ちなみに、今回の問題が紹介されていたCodeIQは、問題を解いて自分をアピールするエンジニア向けのサイトのようです。Googleの入社試験のような感じですね。エレガントなコードを書ける人は、企業からエンジニアとして声をかけられるのでしょうね。今日のわかった最大の素数を探す計算が行われているそうです。数字にすると1742万5170桁だそうです。どんな計算をしたら、こんなに大きな素数を見つけることができるんですかね。なにかしら素数に関する数学の法則があって、余計な計算は省いているんでしょうね。物事の良し悪しを測る尺度として、「ハブとノード」の関係があります。「ヨメレバ」で雑誌を取り扱えるようにしました。その際に、ISBN、JAN、AS...アルゴリズム物の良し悪しを評価する方法Googleは、膨大なインターネット上の情報から、要求した情報をかなりの精度で検...アルゴリズムデーターマイニング最近、データーマイニングについて勉強しています。コメントをキャンセルメールアドレスが公開されることはありません。*サイトスポンサーリンクプロフィール運営者:かん吉サブスリー&市民ランナーグランドスラム達成。