Re: Learning from Eratosthenes
-----BEGIN PGP SIGNED MESSAGE-----
If you think about it, you realize that if you have knocked out all
multiples of the primes less than i, then all numbers left standing
less than i^2 are prime. try with pen and pencil; I figured this one
out in high school. its a common optimization. its also what lets
you stop as soon as you hit the sqrt() of the highest number you want to
check.
On Wed, 11 Oct 2000, Chad Miller wrote:
> > 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.
>
> (Not tested, just eyeballed.)
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3ia
Charset: noconv
iQCVAwUBOesNSMK9HT/YfGeBAQEhMQP/Y7ulHXtsm4v1S7a2b+R2fdz37JpXA/3T
3S7bPy3QLeGhbLyL4mvuFtdVYxcGkuFe8GND03UXKvzt1G8ojvwBCo4xMRljtFSR
ljgnAnlgiDcJrEDaUV2FblW4om8e9YHiOtdQMl16mXVZ1aKI+7lFF7z0vF6DSqgl
BjzxibJovbg=
=CTul
-----END PGP SIGNATURE-----
Reply to: