<br><br><div class="gmail_quote">On Mon, Nov 2, 2009 at 1:59 PM, Will Ness <span dir="ltr"><<a href="mailto:will_n48@yahoo.com">will_n48@yahoo.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">Will Ness <will_n48 <at> <a href="http://yahoo.com" target="_blank">yahoo.com</a>> writes:<br>
<br>
</div><div class="im">> primes = 2: 3: sieve 0 primes' 5<br>
> primes' = tail primes<br>
> sieve k (p:ps) x<br>
> = [x | x <- [x,x+2..p*p-2],<br>
> and [(x`rem`p)/=0 | p <- take k primes']]<br>
> ++ sieve (k+1) ps (p*p+2)<br>
><br>
> (thanks to Leon P.Smith for his brilliant idea of directly generating<br>
> the spans of odds instead of calling 'span' on the infinite odds list).<br>
><br>
</div><div class="im">> The relative performance vs the PQ-version is:<br>
><br>
> 100,000 300,000 1,000,000 primes produced<br>
> 0.6 0.75 0.97<br>
><br>
<br>
</div>One _crucial_ tidbit I've left out: _type_signature_.<br>
<br>
Adding (:: [Int]) speeds this code up more than TWICE!<br>
<br>
:) :)<br></blockquote><div><br></div><div>If you are okay with Int, then maybe you're also happy with Int32 or Word32. If so, why don't you use template haskell to build the list at compile time? If you do that, then getting the kth prime at run-time is O(k). Take that AKS! :)</div>
<div><br></div><div>Jason</div></div>