Golfing Eratosthenes

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?

If you’re interested, here’s an indented/commented copy that might
save a few minutes…

create an array of integers, 2 to 100

a=(2…100).to_a;
p a.each{ |c|

for each element c in that array, if c isn’t nil, it’s prime. so

set multiples of c to nil
a.map!{ |d|
c && d && c<d && d%c == 0 ? nil : d
}
}.compact # finally, print the array minus the nils

I’d appreciate any comments.

Cheers

;Daniel

On 8/2/06, Daniel B. [email protected] wrote:

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…

;D

On 02/08/06, Farrel L. [email protected] wrote:

Any suggestions?
c && d && c<d && d%c == 0 ? nil : d

I got rid of the semi-colons and assigning the arrays (although
technically it’s still ‘assigned’ in the inject) although it might has
made it a bit loner.

Farrel

Gah! Excuse my atrocious spelling and grammar. “…although it has
made it a bit longer”.

On 02/08/06, Daniel B. [email protected] wrote:

}

Daniel B.
http://tiddlyspot.com (free, effortless TiddlyWiki hosting)
http://danielbaird.com (TiddlyW;nks! :: Whiteboard Koala :: Blog ::
Things That Suck)

Here’s my attempt. Note that I have made it a bit more general by
assigning s = 100 beforehand.

(2…(s**0.5)).inject((2…s).to_a){|a,c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact

I got rid of the semi-colons and assigning the arrays (although
technically it’s still ‘assigned’ in the inject) although it might has
made it a bit loner.

Farrel

William J. wrote:

definition of the array a, and do the whole thing with no semicolons.

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}

Hi Ruby Gurus,

Could you please point me how to do some scientific calculation in Ruby:

  1. How to calculate std.dev for an integer array?
  2. Is there a log() function in Ruby?

Thank you!
Austin

Daniel B. wrote:

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}

On 8/2/06, Daniel B. [email protected] wrote:

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

you’d love this one
[*2…100]
:wink:
Cheers
Robert

…swapped to reject, and now I don’t have to test for c and d being


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

On 8/2/06, Wang Austin-W22255 [email protected] wrote:

Hi Ruby Gurus,

Could you please point me how to do some scientific calculation in Ruby:

  1. How to calculate std.dev for an integer array?
  2. Is there a log() function in Ruby?

Thank you!
Austin

  1. I don’t think there’s a builtin function for that, so you’ll have
    to create your own.
    You’ll probably want to add it to the Array class.
    class Array
    def stddev

    your function here

end
end

You could also check rubyforge.org, maybe there’s a statistics library
available there.

  1. Math.log

class Array
def sd(ar)
n = length
sum_sq = inject(0.0) {|accu, v| accu + v*v}
sum = inject(0.0) {|accu, v| accu + v}

Math.sqrt((sum_sq - sum*sum/n) / (n-1))

end
end

On 8/2/06, Wang Austin-W22255 [email protected] wrote:

  1. How to calculate std.dev for an integer array?

try GSL: http://rb-gsl.rubyforge.org/stats.html

J.

Enumerations, all the way :wink:

p (2…100).select{|d|!(2…d-1).find{|c|d%c==0}}

Cheers
Roibert


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

On 02/08/06, William J. [email protected] wrote:

It’s already under 80 chars, but I’d still love to remove 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

On 02/08/06, Robert D. [email protected] wrote:

Enumerations, all the way :wink:

p (2…100).select{|d|!(2…d-1).find{|c|d%c==0}}

You can shave a byte off:

p (2…100).reject{|d|(2…d-1).find{|c|d%c==0}}

Paul.

On 8/2/06, Paul B. [email protected] wrote:

Paul.

Bummer I thaught it was the top ,-)


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

On 02/08/06, Robert D. [email protected] wrote:

you’d love this one
[*2…100]

That’s lovely. Why haven’t I seen it before?!

Paul.

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==0}}

which should qualify, no?

Cheers
Robert

require ‘benchmark’

Benchmark.bm do |benchmark|
user system total real


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

On 8/2/06, Robert D. [email protected] wrote:

the numbers, or is it kind of a generator which violates the rules? Anyway
we could just do the same

----- 8< --------------

Did I get confused with replies here? If so all my appologizes,
I will do it again :wink:

R.

You can shave a byte off:

p (2…100).reject{|d|(2…d-1).find{|c|d%c==0}}

p (2..100).select{|d|(2...d).all?{|c|d%c>0}}

But it has nothing to do with Eratosthenes anymore…

cheers

Simon

On 8/2/06, Kroeger, Simon (ext) [email protected] wrote:

cheers

Simon

You are right, too bad, I was having the time of my life :wink:
But OP’s solution does not either, does it?

here is the famous sieve from Wikipedia, yes I know, you shall not trust
it,
I do not, but as very often this is correct:

  1. Write a list of numbers from 2 to the largest number you want to
    test for primality. Call this List A.

  2. Write the number 2, the first prime number, in another list for
    primes found. Call this List B.

  3. Strike off 2 and all multiples of 2 from List A.

  4. The first remaining number in the list is a prime number. Write
    this number into List B.

  5. Strike off this number and all multiples of this number from List
    A. The crossing-off of multiples can be started at the square of the
    number,
    as lower multiples have already been crossed out in previous steps.

  6. Repeat steps 4 through 6 until no more numbers are left in List A.


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs