From: Robert Dober <robert.dober@...>
Date: 2006-08-02T20:33:33+09:00
Subject: Re: golfing Eratosthenes

------=_Part_69409_33060059.1154518409718
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

>
>
> 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:


Well thank you, I forgot about the sieve, so there is no credit to be taken
for that.
But I am not sure to understand, by using (2..100) at the beginning I have
the numbers, or is it kind of a generator which violates the rules? Anyway
we could just do the same on
[*2..100] where they are *really* there the numbers.

Using Paul's improvement, ty Paul, we would have

p [*2..100].reject{|d|(2..d-1).find{|c|d%c=3D=3D0}}

which should qualify, no?

Cheers
Robert

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!=3Dc&&d%c=3D=3D0};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
>
>


--=20
Deux choses sont infinies : l'univers et la b=EAtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein

------=_Part_69409_33060059.1154518409718--