A number-theoretic sieve that processes a large search range in smaller intervals. To find primes in , first generate the primes at most , then mark their multiples in the current segment. Memory for the segment depends on its width rather than on .
An odd-only segmented sieve represents only odd integers in each bounded interval, handling the prime two separately. For an odd first represented value , array index stands for . To mark multiples of an odd prime , begin at the smallest odd multiple at least and advance by , corresponding to index stride . Base primes up to the square root of the upper endpoint suffice. The segmentation limits working storage while omitting even candidates roughly halves it again. The number one remains nonprime and must be excluded explicitly.

Articles by others on the same topic (0)

There are currently no matching articles.