Re: Learning from Eratosthenes

[Jules Bean <jules@jellybean.co.uk>]

On Wed, Oct 11, 2000 at 11:27:09AM -0400, Chad Miller wrote:
> Offtopic.  Apologies to the uninterested...
> 
> Unless I'm mistaken,
> 
> >               for (j = i * i; j < MAX; j += i)
> >                       map[j >> 3] &= ~(0x80 >> (j&7));
> 
> should be
> 
> >               for (j = i * 2; j < MAX; j += i)
> >                       map[j >> 3] &= ~(0x80 >> (j&7));
> 
> 
> Consider the '3' case.  foo[3] is zero, so we skip to [9] and mark it,
> when we should skip to [6].  There may be some optimization that makes
> skipping to i^2 possible, but I don't yet know it.

Consider this:  You are worried about some number x, smaller than i*i,
but composite. (You can hardly be worried about it if it's
prime). Therefore it has at least two prime factors. If it does indeed 
have i as a prime factor, then the other prime factor is <i, since x < 
i*i. THerefore it has another prime factor <i, so we already 'got' it.

Another way of looking at it: in the sieve, each composite number is
firstly 'got' by it's smallest prime factor.  Therefore it suffices to 
strike out, for each prime p, only numbers for which p is the smallest 
prime factor.  These numbers must all be > p*p.

Hope that helps,

Jules

PS Your Mail-Followup-To header is broken, containing 'cmiller' as
your address.