```Issue #5378 has been updated by Yusuke Endoh.

Status changed from Open to Assigned
Assignee set to Yuki Sonoda

Hello,

Just slowness is not a bug unless it is a regression, I think.
So I moved this ticket to the feature tracker.

I believe that there is no perfect algorithm to enumerate
primes.  Any algorithm has drawback and advantage.  Note that
speed is not the single important thing.  I could be wrong,
but I guess that prime.rb does not priotize speed (especially,
linear-order cost), but high-abstract design.

Even in terms of speed, my version is about 2 times faster
than Peter's, though it uses extra memory.  So, there are

def primes_up_to_yusuke(n)
primes = [2]
n /= 2
prime_table = [true] * n
i = 1
while i < n
if prime_table[i]
primes << j = i * 2 + 1
k = i + j
while k < n
prime_table[k] = false
k += j
end
end
i += 1
end
primes
end

user     system      total        real
primes_up_to_mike  1.720000   0.010000   1.730000 (  1.726733)
primes_up_to_peter  0.780000   0.020000   0.800000 (  0.795156)
primes_up_to_yusuke  0.410000   0.000000   0.410000 (  0.419209)
Prime.each    4.760000   0.010000   4.770000 (  4.765654)

I think every prime-aholic should implement their own favorite
algorithm by himself :-)

--
Yusuke Endoh <mame / tsg.ne.jp>
----------------------------------------
Feature #5378: Prime.each is slow
http://redmine.ruby-lang.org/issues/5378

Author: Mike Conigliaro
Status: Assigned
Priority: Normal
Assignee: Yuki Sonoda
Category:
Target version:

See discussion here: https://gist.github.com/1246868

require 'benchmark'
require 'prime'

def primes_up_to(n)
s = [nil, nil] + (2..n).to_a
(2..(n ** 0.5).to_i).reject { |i| s[i].nil? }.each do |i|
(i ** 2).step(n, i) { |j| s[j] = nil }
end
s.compact
end

Benchmark.bm(12) do |x|
x.report('primes_up_to') { primes_up_to(2000000).inject(0) { |memo,obj| memo + obj } }
x.report('Prime.each') { Prime.each(2000000).inject(0) { |memo,obj| memo + obj } }
end

\$ ruby -v
ruby 1.9.2p290 (2011-07-09 revision 32553) [x86_64-darwin10.8.0]
\$ ruby lol.rb
user     system      total        real
primes_up_to  1.470000   0.020000   1.490000 (  1.491340)
Prime.each    7.820000   0.010000   7.830000 (  7.820969)

--
http://redmine.ruby-lang.org

```