### This One's a Sieve

 on Mar 31, 2015 at 15:17 UTC 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 (Archbishop) 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

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: obfuscated [id://1122008]
Approved by Athanasius
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2022-01-18 22:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2022, my preferred method to securely store passwords is:

Results (54 votes). Check out past polls.

Notices?