Re: Learning from Eratosthenes

[Santiago Vila <sanvila@unex.es>]

On Wed, 11 Oct 2000, Chad Miller wrote:

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

You can skip 6 for the '3' case because it was already considered
in the '2' case (since 2*3=6). That's why i*i is enough.