note
tye
<p>
[tilly]'s comment about things being "nearly linear" threw me for a bit. Then I realized that the quadratic nature is countered by the outer loop only needing to run to sqrt(N) and the inner loop being somewhat similarly restricted.
</p><p>
Which made me realize that my solution was suboptimal. Here is a faster one at the same number of characters [ thanks to [MeowChow] noting that I'd stupidly left in a trailing semicolon in my previous one ;) ]:
<code>sub sieve3 {
grep{@_[map$a*$_,$_..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop
} # ^^
for( @ARGV ) {
print "$_: ",join(" ",sieve3($_)),$/;
}
</code></p><p>
In playing with this and verifying that I didn't break it, I noticed something interesting and expanded on it. For how long of a stretch can you go without hitting any prime numbers? Well, stopping at 0.5million (because of memory limits), here are the results. "xN" means there were N ties before a new "winner" appeared:
<code>2=53(x2) # 3..5, 5..7
4=117(x3) # 7..11, 13..17, 19..23
6=2923(x7)
8=9789
14=127113(x3)
18=541523
20=907887
22=11511129
34=13611327(x2)
36=95879551(x3)
44=1572715683
52=1966119609(x2)
72=3146931397
86=156007155921(x2)
96=360749360653
112=370373370261
114=492227492113
</code>
</p>

<a href="/index.pl?node=tye&lastnode_id=1072">tye</a>
(but my friends call me "Tye")
81695
81750