C Erler
9/28/2006 3:47:00 AM
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!