Will Ness will_n48 at yahoo.com
Wed Dec 30 14:46:57 EST 2009

```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).

```