Talk:Trial division (C)

From LiteratePrograms

There is a whole research area in prime sieves, but still, there are some simple things that can be done to speed up the sieve. This line

 for(j = i + i; j <= max; j += i)

may be changed to this:

 for(j = i*i; j <= max; j += 2*i)

assuming that we eliminate the multiples of 2 in a preprocessing step.

Also, by changing the primes list so that it is terminated with 2^16-1 instead of 0, one can eliminate the test for zero in the loop header of the verion of the trial division factorer that uses the primes list.