golfing Eratosthenes

[Daniel Baird]

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

 

[Daniel Baird]

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

;D

 

[Farrel Lifson]

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


--
Daniel Baird
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

 

[Farrel Lifson]

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

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

 

[William James]

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}

 

[William James]

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}

 

[Wang Austin-W22255]

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=20

 

[Sander Land]

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.

2) Math.log

 

[Paul Battley]

you'd love this one
[*2..100]

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

Paul.

 

[jogloran]

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

 

[Jan Svitok]

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

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

J.

 

[Farrel Lifson]

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

 

[Paul Battley]

Enumerations, all the way

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.

 

[Chad Perrin]

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}

Of course, one might make a case for making that (2..99), shaving off a
byte, since we all know 100 isn't prime. We could make that 99 lower,
but there's no point if our point is golfing.