On 22 Jun 99, at 20:14, Cyril Flaig wrote:
> Could someone explain me how the sieve table works?
OK. If you can follow C code fragments then the following should be
at least as clear as a whole heap of words.
int i;
char * sieve;
char * sptr;
sieve = (char *) malloc(255255);
for ( sptr=sieve, i=0 ; i<255255 ; sptr++, i++ )
* sptr = 1;
for ( sptr=sieve, i=0 ; i<255255 ; sptr+=3, i+=3 )
* sptr = 0;
for ( sptr=sieve, i=0 ; i<255255 ; sptr+=5, i+=5 )
* sptr = 0;
for ( sptr=sieve, i=0 ; i<255255 ; sptr+=7, i+=7 )
* sptr = 0;
for ( sptr=sieve, i=0 ; i<255255 ; sptr+=11, i+=11 )
* sptr = 0;
for ( sptr=sieve, i=0 ; i<255255 ; sptr+=13, i+=13 )
* sptr = 0;
for ( sptr=sieve, i=0 ; i<255255 ; sptr+=17, i+=17 )
* sptr = 0;
The above is initialization code which only needs to be executed
once.
We now have a table pointed to by sieve in which the j'th element is
non-zero only if j is not divisible by 3, 5, 7, 11, 13 or 17 (the six
smallest odd prime numbers. 2 does not worry us since a factor of
2^p-1 obviously must be odd) - provided 0 <= j < 255255.
Now 3 * 5 * 7 * 11 * 13 * 17 = 255255, so, if we want to see if a
candidate factor f is divisible by any of 3, 5, 7, 11, 13, 17, all we
have to do is to look in the (f % 255255)'th element of the sieve
table. i.e. go on to do further checks on the factor if
sieve[f % 255255] != 0.
If you like pure pointer notation then instead read
* (sieve + (f % 255255)) != 0.
Got it?
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
