スポンサーサイト

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

エラトステネスの篩 Ruby編

エラトステネスの篩 (ふるい) によって素数を列挙する Ruby プログラムの例。

プログラム例

#!ruby -Ks

# Sieve of Eratosthenes
# list of prime numbers at most n
def sieve(n) 
  primes = []
  if n < 2 then
    return primes;
  end

  # 2 は素数
  primes << 2
  if n < 3 then
    return primes;
  end

  # 奇素数を列挙する
  lastidx = (n - 3) / 2
  flag = Array.new( lastidx + 1, true )  # すべてに true をセット
  0.upto(lastidx) { |i|
    if flag[i] then
      p = 2 * i + 3  # 添字 i は 2*i+3 に対応
      primes << p
      if p <= n / p then
        # 残った最小の数を残し、その倍数をすべて取り除く
        (i + p).step( lastidx, p ) { |j|
          flag[j] = false
        }
      end
    end
  }

  primes
end

if __FILE__ == $0

  # 50以下の素数を列挙する
  sieve(50).each{ |p| 
    print("#{p} ")
  }

end

実行結果:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 

関連記事

エラトステネスの篩のプログラム例 まとめ

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。