If I do all the sieving in one stretch, a naive implementation of the
Atkin sieve is actually faster than the Prime class in ruby 1.9.  The
Prime class has to do it in blocks (it never knows quite how many
primes someone will ask for), and it seems that I've handled that
reorganization badly.

Here is a naive, all-in-one-stretch version (faster than Prime in 1.9)
:

limit = 500000
primes = Array.new(limit + 1) { false }

(1..limit ** 0.5).each do |x|
  x_sq = x**2
  (1..limit ** 0.5).each do |y|
    y_sq = y**2
    n = 4*x_sq + y_sq
    primes[n] = (not primes[n]) if (n <= limit and (n % 12 == 1 or n %
12 == 5))
    n = 3*x_sq + y_sq
    primes[n] = (not primes[n]) if (n <= limit and n % 12 == 7)
    n = 3*x_sq - y_sq
    primes[n] = (not primes[n]) if (n <= limit and x > y and n % 12 ==
11)
  end
end

primes.each_index do |i|
  primes[i] =
    if primes[i]
      i_sq = i**2
      i_sq.step(limit, i_sq) do |prime_square_mult|
        primes[prime_square_mult] = false
      end
      i
    else
      nil
    end
end

primes[2] = 2
primes[3] = 3
primes.compact!