This One's a Sieve

[Schmunzie]

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[$_]}

[Athanasius]

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

Read more... (1312 Bytes)

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,

[danaj]

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

[Anonymous Monk]

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

[ambrus]

We'd better link to Not a Sieve

[Grimy]

Oh, is it golf?

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

Somewhat slower than the original, but 42 characters =p