[Haskell-cafe] Re: FASTER primes

[Will Ness]

Daniel Fischer <daniel.is.fischer <at> web.de> writes:

> 
> 
> Am Dienstag 29 Dezember 2009 20:16:59 schrieb Daniel Fischer:
> > > especially the claim that going by primes squares
> > > is "a pleasing but minor optimization",
> >
> > Which it is not. It is a major optimisation. It reduces the algorithmic
> > complexity *and* reduces the constant factors significantly.
> 
> D'oh! Thinko while computing sum (takeWhile (<= n) primes) without paper.
> It doesn't change the complexity, and the constant factors are reduced 
> far less than I thought. 


I do not understand. Turner's sieve is

  primes = sieve [2..]
   where
    sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p /= 0]

and the Postponed Filters is

  primes = 2: 3: sieve (tail primes) [5,7..]
   where 
    sieve (p:ps) xs = h ++ sieve ps [x | x<-t, x `rem` p /= 0]
                      where (h,~(_:t)) = span (< p*p) xs  

Are you saying they both exhibit same complexity? I was under impression that 
the first shows O(n^2) approx., and the second one O(n^1.5) (for n primes 
produced).