This has been an interesting thread to follow.
I played around with a Bit Vector algorithm... going for efficiency at the cost of a little brevity.
Here's what I came up with:
#!usr/bin/perl -w
use Benchmark;
timethese(100,{
Adam => sub {
@_=(1);
L:for(2..1000) {
$i=-@_; #updated per node 20757 7/13/2000
while(++$i){ #ditto
next L if!($_%$_[$i])
}
push@_,$_
}
#print join "\t", @_;
},
Maverick => sub {
for(1..1000){
push@_,$_;
for(@_[1..$#_-1]){
pop@_&&last if!($_[-1] %$_)
}
}
#print join "\t", @_;
},
Ase => sub {
$v='1' x 1000;
for(2..1000){
next if !vec($v,$_-1,8);
for($q=$_*2;$q<1001;$q+=$_){
vec($v,$q-1,8)=0
}
}
#print join "\t",grep {vec($v,$_-1,8)} (1..1000);
},
});
Here's a table summarizing the data:
Routine | N | Iterations | Time |
Adam | 1000 | 100 | 5 |
Ase | 1000 | 100 | 2 |
Maverick | 1000 | 100 | 2 |
Adam | 10000 | 100 | 203 |
Ase | 10000 | 100 | 21 |
Maverick | 10000 | 100 | 24 |
Ase | 100000 | 100 | 221 |
Maverick | 100000 | 100 | 236 |
Benchmark is your friend!
It seems Mavericks code is only very slightly slower with the benefit of being slightly shorter.
This was done on a 300 mHz amd K6 running win 98 and perl 5.005_02 (activestate 509) as always your mileage may vary.
Update 7/13/2000: I modified Adam's code per this node and re-benchmarked accordingly.
-ase