Hi,

Am Samstag, 25. Jul 2009, 05:27:07 +0900 schrieb Lloyd Linklater:
> I am writing a little thing to find all the prime numbers to a million.

Here is one that works:

  def sieve max
    a = Array.new max do |i| i end
    a.shift
    a.shift
    i = 0
    while (t = c = a[i]) do
      yield c if block_given?
      while (t += c) <= max do a.delete t end
      i += 1
    end
    a
  end

And this one is fast enough:

  def sieve max
    if block_given? then
      h = {}
      2.upto max do |c|
        unless h[ c] then
          yield c
          t = c
          while (t += c) <= max do h[ t] = true end
        end
        c += 1
      end
    else
      a = []
      sieve max do |p| a.push p end
    end
  end

Bertram


-- 
Bertram Scharpf
Stuttgart, Deutschland/Germany
http://www.bertram-scharpf.de