<< 何年越しだか | main | ProjectEuler_Problem010 >>
スポンサーサイト
0

    一定期間更新がないため広告を表示しています

    カテゴリ:- | | - | - |
    Problem007
    0
      JUGEMテーマ:数学



      今日はProject EulerのProblem007に手を出した。

      10001番目の素数を求めよ。という問題。

      単純に1から素数かどうかをチェックしていくプログラムを書いたけど遅い。

      多少の工夫はしているけど、ほぼ素直に組んだ。

      改善の余地がありそうなのは、

      Nが素数かどうか判定するために、1から順に数字をカウントアップしていき

      すべての数で割り切れなければ素数と判定しているのだけど
      (実際は、奇数のみチェックし、カウントアップもN/2でやめている)

      やはり無駄が多い気がする。

      どこまでの数をチェックするのが妥当なのだろうか。

      というよりは、小さいほうから割っていくのだから、たとえば

      3と5で割り切れない場合は15で割ってみる必要はないのだけど

      それをやってしまっている。

      動的にカウントアップの上限値を変えるようにすればよいのだろうか?


      エラトステネスのふるいに倣って実装してみたら早いのかな。。。

      まぁでもできたので良し。

      一応、以下ソース。

      #############################################################################
      #
      #  Project Euler Problem6
      #  10001 番目の素数を求めよ.
      #
      ############################################################################

      #素数チェックするメソッド
      #num:素数かどうか反転したい数
      def CheckPrime(num)
        #2は偶数で唯一の素数
        if num == 2 then
          return true
        end
        #2以降の偶数はすべてfalse
        if num%2==0 then
          return false
        end
        i = 3
        #チェックしたい数の半分までで十分
        while i <= num /2#上限の値を動的にするともう少し早くなるかな
           if num%i == 0 then
             return false
           else
             #偶数はとばすので2カウントアップ
             i = i+2
           end
        end 
        #ここまで来たら素数確定
        return true
      end

      #素数の数の初期化
      count = 0
      #1はとばして2から素数かどうかをチェックする
      factor = 2
      while true
        if CheckPrime(factor) then
          count = count + 1
          #print("The ",count, "th Prime Number is ",factor ,"¥n" )
        end
        if count == 10001 then
          break
        end
          factor = factor + 1#ここも改良できる
      end

      print("The ",count, "th Prime Number is ",factor ,"¥n" )




       

      カテゴリ:Project Euler | 23:47 | comments(2) | trackbacks(0) |
      スポンサーサイト
      0
        カテゴリ:- | 23:47 | - | - |
        コメント
        Project Euler につられてやってきました。
        私も素人ながら、挑戦している者です。

        偶然にも、同じRubyを使ってます。

        また覗かせていただきます。
        | shokeizen | 2013/02/23 9:26 PM |
        >shokeizenさん
        コメントありがとうございます。
        なかなか更新できませんがよろしくお願いします。
        shokeizenさんのブログもまた拝見させていただきたいと思います。
        | tom | 2013/02/25 9:51 PM |
        コメントする









        この記事のトラックバックURL
        http://coffee-donut.jugem.jp/trackback/30
        トラックバック