# Golfing Eratosthenes

**URL:** <https://www.ruby-forum.com/t/golfing-eratosthenes/101063>\
**Category:** Ruby\
**Created:** [August 3, 2006, 12:09pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063 "2006-08-03T12:09:20Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:09pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/1 "2006-08-03T12:09:20Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:11pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/2 "2006-08-03T12:11:11Z")

</div>

On 8/2/06, Daniel B. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:12pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/3 "2006-08-03T12:12:02Z")

</div>

On 02/08/06, Farrel L. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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”.

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:11pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/4 "2006-08-03T12:11:35Z")

</div>

On 02/08/06, Daniel B. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> ## }
> 
> Daniel B.  
> [http://tiddlyspot.com](http://tiddlyspot.com) (free, effortless TiddlyWiki hosting)  
> [http://danielbaird.com](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

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:18pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/5 "2006-08-03T12:18:51Z")

</div>

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}

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:20pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/6 "2006-08-03T12:20:32Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:18pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/7 "2006-08-03T12:18:33Z")

</div>

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}

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:22pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/8 "2006-08-03T12:22:37Z")

</div>

On 8/2/06, Daniel B. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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.

- Albert Einstein

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:23pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/9 "2006-08-03T12:23:09Z")

</div>

On 8/2/06, Wang Austin-W22255 [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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](http://rubyforge.org), maybe there’s a statistics library  
available there.

1. Math.log

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:23pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/10 "2006-08-03T12:23:45Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:24pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/11 "2006-08-03T12:24:00Z")

</div>

On 8/2/06, Wang Austin-W22255 [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

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

try GSL: [http://rb-gsl.rubyforge.org/stats.html](http://rb-gsl.rubyforge.org/stats.html)

J.

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:24pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/12 "2006-08-03T12:24:29Z")

</div>

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.

- Albert Einstein

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:24pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/13 "2006-08-03T12:24:53Z")

</div>

On 02/08/06, William J. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:25pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/14 "2006-08-03T12:25:08Z")

</div>

On 02/08/06, Robert D. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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.

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:25pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/15 "2006-08-03T12:25:35Z")

</div>

On 8/2/06, Paul B. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:23pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/16 "2006-08-03T12:23:33Z")

</div>

On 02/08/06, Robert D. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

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

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

Paul.

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:25pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/17 "2006-08-03T12:25:58Z")

</div>

> 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

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:26pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/18 "2006-08-03T12:26:17Z")

</div>

On 8/2/06, Robert D. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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.

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:27pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/19 "2006-08-03T12:27:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![danielb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c57346/32.png) [@danielb](https://www.ruby-forum.com/u/danielb)\
**Post date:** [August 3, 2006, 12:28pm UTC](https://www.ruby-forum.com/t/golfing-eratosthenes/101063/20 "2006-08-03T12:28:20Z")

</div>

On 8/2/06, Kroeger, Simon (ext) [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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:

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

[Next page](https://www.ruby-forum.com/t/golfing-eratosthenes/101063.md?page=2)