Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

This One's a Sieve

by Schmunzie (Sexton)
on Mar 31, 2015 at 15:17 UTC ( #1122008=obfuscated: print w/replies, xml ) Need Help??

hdb recently pointed out that I had misremembered how the Sieve of Eratosthenes works so now I'm having another go. Not all that obfu'd but moderately golfed.

$m=250;for(2..$m){for($a=$_*2;$a<=$m;$a+=$_){$c[$a]++}print"$_,"x!$c[$_]}

Replies are listed 'Best First'.
Re: This One's a Sieve
by Athanasius (Chancellor) on Apr 01, 2015 at 15:27 UTC

    Nice! But the pedant in me feels compelled to point out that for a 35% increase in length, this obfu can be made significantly more time-efficient:

    $m=250;print 2;for($b=3;$b<=$m;$b+=2){if(!$d[$a]){for($a=$b*$b;$a<=$m; +$a+=$b){$c[$a]=1}}print",$b"}

    The speed increase is negligible for low values of $m, but for large value it becomes significant (e.g. an increase of nearly 8 times in speed for $m equal to ten million):

    But note that this version is still inefficient. See johngg’s recent post: Re^3: Number functions I have lying around, which saves on (1) cpu time by iterating only up to sqrt($m), and (2) memory by storing the sieve in a bit vector.

    Hope this is of interest,

    Athanasius <°(((><contra mundum Iustus alius egestas vitae, eros Piratica,

      Or better yet, one of the sieves shown on RosettaCode, which are 2.5 to 8 times faster than the johngg sieve.

        Still better, the version that's idiomatic, clean, and more performant than anything on RosettaCode at the present time.

Re: This One's a Sieve
by ambrus (Abbot) on Apr 02, 2015 at 10:45 UTC
Re: This One's a Sieve
by Grimy (Pilgrim) on May 07, 2015 at 14:56 UTC

    Oh, is it golf?

    print$"while($\)=@==@=?grep$_%$\,@=:2..250

    Somewhat slower than the original, but 42 characters =p

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: obfuscated [id://1122008]
Approved by Athanasius
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (5)
As of 2018-07-19 15:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    It has been suggested to rename Perl 6 in order to boost its marketing potential. Which name would you prefer?















    Results (411 votes). Check out past polls.

    Notices?