Help understanding eratosthenes sieve implementation

Question

I found this LINQ implementation of the eratosthenes sieve on this website. I understand the basic concept of the sieve, but there's one detail I don't get. What is the purpose of the first Enumerable.Range(0,168)?

List<int> erathostheness = Enumerable.Range(0, 168)
.Aggregate(Enumerable.Range(2, 1000000).ToList(), (result, index) =>
{
    result.RemoveAll(i => i > result[index] && i % result[index] == 0);
    return result;
}).ToList();

Answer 1

It is the number of times the sieve will be run to eliminate all non-primes from the list.

result.RemoveAll(i => i > result[index] && i % result[index] == 0);

Each time you run the sieve, this line of code takes the smallest number in the list (the smallest prime that the result hasn't had all its multiples removed of yet) and then removes all the multiples. This is run 168 times, and on the 168th time the smallest number the list hasn't been screened of yet is 997, which naturally is the 168th prime.

This only needs to be run 168 times because all numbers can be expressed as the product of a list of primes, and there is no number less than 1000000 that is a multiple of the 169th primes number (1,009) that is NOT a multiple of a prime lower than 1009. The lowest number that this would removed by sieving out 1009 that has NOT been removed already is 1009 * 1013 = 1,022,117, or the 169th primes multiplied by the 170th prime, which is clearly greater than 100000 and thus doesn't need to be checked for this set of numbers.

Hence, all the multiples of 1009 have already been removed from the list when you get to that point, so there's no point in continuing as you already have removed all the non-primes from the list. :D

Answer 2

There are 168 primes less that 1000.

If x is less than 1,000,000, and x is not prime, then x can be factored into prime numbers p1, p2, ..., pn. At least one of these factors must be less that 1000, or else the product would be more than 1,000,000. This means at least one factor must be one of the first 168 primes.