From: Farrel Lifson <farrel.lifson@...>
Date: 2006-08-02T20:12:09+09:00
Subject: Re: golfing Eratosthenes

On 02/08/06, William James <w_a_x_man@yahoo.com> wrote:
> William James wrote:
> > Daniel Baird wrote:
> > > On 8/2/06, Daniel Baird <danielbaird@gmail.com> wrote:
> > > > Hi all,
> > > >
> > > > I've been golfing around with the sieve of Eratosthenes.  Here's what
> > > > I've got so far:
> > > >
> > > > a=(2..100).to_a;p a.each{|c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact
> > > >
> > > > It's already under 80 chars, but I'd still love to remove the
> > > > definition of the array a, and do the whole thing with no semicolons.
> > > > Any suggestions?
> > > >
> > >
> > > Improvement:
> > >
> > > a=(2..100).to_a;p a.each{|c|a.reject!{|d|c<d&&d%c==0}}
> > >
> > > .swapped to reject, and now I don't have to test for c and d being
> > > nil, or do the final  compact.  Seems ok even though I'm editing the
> > > array I'm looping through..
> >
> > p (2..100).inject([]){|a,n|a.any?{|i|n%i==0}?a:a<<n}
>   p (2..100).inject([]){|a,n|a.any?{|i|n%i<1}?a:a<<n}
>
>
>

While that's an elegant looking solution it is not a 'true' sieve. It
builds up the primes array rather than eliminating non-primes from an
existing array.It's seems to be quite a bit slower:

require 'benchmark'

def build(max)
  (2..max).inject([]){|a,n|a.any?{|i|n%i<1}?a:a<<n}
end

def sieve(max)
	[*2..max**0.5].inject([*2..max]){|a,c|a.reject!{|d|d!=c&&d%c==0};a}
end

Benchmark.bm do |benchmark|
  benchmark.report("Build:"){build(ARGV[0].to_i)}
  benchmark.report("Sieve:"){sieve(ARGV[0].to_i)}
end

C:\Documents and Settings\flifson\My Documents>ruby primes.rb 1000
      user     system      total        real
Build:  0.047000   0.000000   0.047000 (  0.047000)
Sieve:  0.016000   0.000000   0.016000 (  0.015000)

C:\Documents and Settings\flifson\My Documents>ruby primes.rb 10000
      user     system      total        real
Build:  1.672000   0.000000   1.672000 (  1.688000)
Sieve:  0.359000   0.000000   0.359000 (  0.359000)

C:\Documents and Settings\flifson\My Documents>ruby primes.rb 100000
      user     system      total        real
Build: 96.437000   0.000000  96.437000 (102.107000)
Sieve:  8.547000   0.015000   8.562000 (  8.656000)

Farrel