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
Hi Ruby Gurus,
Could you please point me how to do some scientific calculation in Ruby:
- How to calculate std.dev for an integer array?
- 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]
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.
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:
- How to calculate std.dev for an integer array?
- Is there a log() function in Ruby?
Thank you!
Austin
- 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.
- 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:
- How to calculate std.dev for an integer array?
try GSL: http://rb-gsl.rubyforge.org/stats.html
J.
Enumerations, all the way 
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.
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
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.
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.
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
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
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:
-
Write a list of numbers from 2 to the largest number you want to
test for primality. Call this List A.
-
Write the number 2, the first prime number, in another list for
primes found. Call this List B.
-
Strike off 2 and all multiples of 2 from List A.
-
The first remaining number in the list is a prime number. Write
this number into List B.
-
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.
-
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.