[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: Learning from Eratosthenes

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.

(Not tested, just eyeballed.) 

						- chad

Chad Miller <cmiller@surfsouth.com>   URL: http://web.chad.org/   (GPG)
"Any technology distinguishable from magic is insufficiently advanced".
First corollary to Clarke's Third Law (Jargon File, v4.2.0, 'magic')

Reply to: