HLL sieve example

[Jecel Mattos de Assumpcao Jr.]

On Sat, 11 Mar 95 2:06:33 MET Francois-Rene Rideau wrote:
> Jecel said:
> > I don't see any difference between the "lame" C version of the
> > sieve algorithm and the message passing with side effects on.
> >
> > In fact, the lame C version does not look at all like C...
>    Well, actually, I've not have time to edit it at all; I just
> copypasted the version below. Feel free to contribute patches to this file,
> as well as to any file in the project !

Ok. I just thought that it was correct and I was missing the point.
I'll type in a C Sieve from Byte at this point :-)

Byte, January 1983, page 306
Listing 11: A further imporved Sieve program in C. This program saves
time by blanking out multiples of primes starting at the square of the
prime rather than at the prime times 3. Unlike the other programs, this
program uses multiplication.

/* A C version of the Sieve program as suggested by KNUTH */
/*  (uses a multiple, though) */
#define true 1
#define false 0
#define size 8190
char flags[size + 1];
int i,k,prime,count,iter,strikout;

main()
{
    printf("10 iterations\n");
    for(iter = 1; iter <= 10; iter ++) {
        strikout = true;
        count = 0;
        for(i = 0; i <= size; i++) flags[i] = true;
        for(i = 1; i <= size; i++) {
            if(flags[i]) {
                prime = i + i + 1;
/*              printf(" %d",prime); */
                count++;
                if(strikout) {
                    if((k = ((prime*prime)-1) >> 1) < size)
                        for(; k <= size; k += prime)
                            flags[k] = false;
                     else {
                         strikout = false;
                         continue;
                     }
                }
            }
        }
    }
    printf("\n%d is the largest of %d primes.",prime,count);
}


Not quite a ready-to-use patch, but at least you don't have to
type it in. Please note that the ugly formatting conventions and
inconsistent spacing is the author's ( Jim Gilbreath and Gary
Gilbreath ) and not mine.

-- Jecel