スポンサーサイト

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

[Ruby][アルゴリズム入門]エラトステネスのふるい

第一章「ウォーミングアップ」 目次

1-0 アルゴリズムとは
1-1 漸化式
1-2 写像
1-3 順位付け
1-4 ランダムな順列
1-5 モンテカルロ法
1-6 ユークリッドの互除法
1-7 エラトステネスのふるい

素数の判定

nが素数か否か判定する。

ルートn以上の数字は調べる必要はない。
# encoding: cp932

while (print "data? "; n = gets.chomp; n != "")
  prime = true
  if (n = n.to_i) >= 2
    limit = Math.sqrt(n).to_i
    limit.downto(2) do |i|
      if (n % i) == 0
        prime = false
        break
      end
      prime = true
    end
    if prime
      puts "素数"
    else
      puts "素数じゃない"
    end
  end
end


2~Nの全ての素数

2~Nまでの整数の中から全ての整数を求める。
# encoding: cp932

NUM = 1000
pri = Array.new(NUM / 2 + 1)
m = 0

2.upto(NUM) do |n|
  prime = true
  if n >= 2
    limit = Math.sqrt(n).to_i
    limit.downto(2) do |i|
      if (n % i) == 0
        prime = false
        break
      end
    end
    if prime
      pri[m] = n
      m += 1
    end
  end
end

m.times do |i|
  puts pri[i]
end


エラトステネスのふるい

上記素数の判定アルゴリズムでは、繰り返し回数がn√n/2 (平均値)となる。効率的に素数を求める方法として「エラトステネスのふるい」がある。この方法を用いて2~Nの中から素数を全て求める。
1:2~Nの数をすべて「ふるい」に入れる
2:「ふるい」の中で最小値を素数とする。(この場合2)
3:今求めた素数の倍数をすべて「ふるい」から外す。
4:2~3をnまで繰り返し「ふるい」に残った数が素数である。
# encoding: cp932

NUM = 1000
pri = Array.new(NUM + 1)
2.upto(NUM){|i| pri[i] = 1 }

limit = Math.sqrt(NUM).to_i

2.upto(limit) do |i|
  if pri[i] == 1
    2.upto(NUM) do |j|
      pri[j] = 0 if j % i == 0
    end
  end
end

2.upto(NUM) do |i|
  puts i if pri[i] == 1
end


素因数分解

nを素因数分解する。

1:まず、nを2で割り切れなくなるまで繰り返し割っていく。その際、割り切れなくなる度に2を表示する。
2:悪数を3として同じことを繰り返し、以降4,5,6,……と続けて行く。実際は素数について調べればいいのだが、素数表がないため手当たり次第に調べている。しかし、素数以外の物で割る場合は、それ以前にその数を素因数分解した時の素数ですでに割られているので、割り切れることはない。
3:割る数をαとしたとき、√n>=α(n>=α×α)の間が2を繰り返す条件である。nの値も割られる度に小さくなっている。
# encoding: cp932

while (print "data? "; n = gets.chomp; n != "")
  a = 2
  n = n.to_i
  while n >= (a * a)
    if n % a == 0
      print "#{a}*"
      n /= a
    else
      a += 1
    end
  end
  puts n
end

テーマ : プログラミング - ジャンル : コンピュータ

コメント
コメントの投稿
管理者にだけ表示を許可する

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