Return to Question

The digests for verifying the sieve output have been computed from reliable sources, as indicated in the topic Checksumming large swathes of prime numbers? (for verification). Sources:

The digests for verifying the sieve output have been computed from reliable sources, as indicated in the topic Checksumming large swathes of prime numbers? (for verification). Sources:

The first use of segmentation is to avoid unnecessary work when the start of the range to be sieved is higher than the square root of the upper end of the range, like in SPOJ problem #2 PRIME1. Sieving all the way up to the upper end of the range (10^9 for PRIME1) can easily exceed the time limit of 5 seconds; by contrast, sieving only the potential factors up to the square root and then the actual target range is several thousand times as fast. The second use of segmentation is for speeding up the sieving of bigger ranges but that is explained below, with the code for extending the factor sieve.

The first use of segmentation is to avoid unnecessary work when the start of the range to be sieved is higher than the square root of the upper end of the range, like in SPOJ problem #2 PRIME1. Sieving all the way up to the upper end of the range (10^9 for PRIME1) can easily exceed the time limit of 5 seconds; by contrast, sieving only the potential factors up to the square root and then the actual target range is several thousand times as fast. This is pretty much the only way of sieving close to 2^64 without taking a long holiday... The second use of segmentation is for speeding up the sieving of bigger ranges but that is explained below, with the code for extending the factor sieve.

Idiosyncratic coding choice #1: as you can see, I calculate many values into separate variables with relatively long (but hopefully accurate) names. This gives the calculation of these values several times as much source code space as elsewhere, where the stuff might be crammed into big expressions and loop headers. But elsewhere these calculations are rarely accurate. Besides, I'm using this as some sort of 'live' (executable) documentation for myself of how the stuff works. Most, if not all, Eratosthenes coding errors actually occur with indexing-related math, so I thought this might be appropriate here as well.

Idiosyncratic coding choice #1: as you can see, I calculate many values into separate variables with relatively long (but hopefully accurate) names. This gives the calculation of these values several times as much source code space as elsewhere, where the stuff might be crammed into big expressions and loop headers. But elsewhere these calculations are often not very accurate. Besides, I'm using this as some sort of 'live' (executable) documentation for myself of how the stuff works. Most, if not all, Eratosthenes coding errors actually occur with indexing-related math, so I thought this might be appropriate here as well.