Re: RE: sieve of Eratosthenes

[cforde]

in reply to RE: sieve of Eratosthenes
in thread sieve of erothenes

In the pursuit of efficiency I have come up with a slightly different implementation: Carl1. In Carl2 I tried to optimize at the expense of a few more characters.

On my WinNT PIII 800Mhz machine with ActiveState 522 both of these are faster than ase's Bit Vector implementation.

  Carl1:
    @p=(1);for(2..10000){if(!$n[$_]){push@p,$_;for($k=$_*$_;$k<=10000;
+$n[$k]=1,$k+=$_){}}}

  Carl2:
    @p=(1,2);for($_=3;$_<=10000;$_+=2){if(!$n[$_]){push@p,$_;for($k=$_
+*$_;$k<=10000;$n[$k]=1,$k+=$_){}}}

One thing that I found interesting is that for n less than about 10,000, Carl1 is significantly faster than Carl2. The loop control overhead must be pretty significant.

Have fun,
Carl Forde