4

私は想像できるすべてのサイトを検索しましたが、ruby1.8がmathnの下のPrimeクラスの素数のリストを作成するために使用する基本アルゴリズムを決定できません。以下は、（100番目の素数を見つけるために）100回呼び出されるsucメソッドの実行可能なバージョンです。誰かがこれがどのように機能するか知っていますか？

number_of_primes = 100

seed = 1
primes = Array.new
counts = Array.new


while primes.size < number_of_primes
  i = -1
  size = primes.size
  while i < size
    if i == -1
      seed += 1
      i += 1
    else
      while seed > counts[i]
        counts[i] += primes[i]
      end
      if seed != counts[i]
        i += 1
      else
        i = -1
      end
    end
  end
  primes.push seed
  counts.push (seed + seed)
end

puts seed

もちろん、実際のコードは次のとおりです。http: //ruby-doc.org/stdlib-1.8.7/libdoc/mathn/rdoc/Prime.html

ふるいにかける事前定義されたリストがないため、ふるいアルゴリズムのようには見えません。除算またはモジュラス演算がないため、試行除算アルゴリズムではありません。私は完全に困惑しています。

4

1 に答える 1

5

アルゴリズムはエラトステネスのふるいに基づいています。

seed素数についてテストされる整数です。primesは、よりも小さい素数のリストであり、よりも大きい対応する最小公倍数を保持しseedます。countsseed

「次の」取り消し線付きの数字のリストと考えてくださいcounts。ただし、プライムごとに1つだけで、常に更新されます。次に大きい倍数を見つけるとき、正確に得られればseed、それは素数ではないので、外側のループをリセットします（でi=-1）。

正確に遭遇することなく、より大きな倍数のリストを更新した場合にのみ、それが素数であるとseed推測できます。seed

少し簡略化してコメントしたコードは次のとおりです。

number_of_primes = 100

seed = 1
primes = []
counts = []

while primes.size < number_of_primes
  seed += 1
  i = 0
  while i < primes.size      # For each known prime
    while seed > counts[i]   # Update counts to hold the next multiple >= seed
      counts[i] += primes[i] # by adding the current prime enough times
    end
    if seed != counts[i]
      i += 1    # Go update next prime
    else
      i = 0     # seed is a multiple, so start over...
      seed += 1 # with the next integer
    end
  end
  # The current seed is not a multiple of any of the previously found primes, so...
  primes.push seed
  counts.push (seed + seed)
end

puts seed
于 2012-12-08T06:34:03.207 に答える