Help to understand the implementation of the sieve of eratosthenes

Question

I found this LINQ implementation of eratosthenes sieve on this website. I understand the basic concept of the sieve, but there is one detail that I don’t get. What is the purpose of the first Enumerated Rank (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

This is the number of times the sieve will start to exclude all non-prime numbers from the list.

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

Each time you start the sieve, this line of code takes the smallest number in the list (the smallest number in which result has not yet removed all its multiples), and then removes all the multiples. This is done 168 times, and for the 168th time the smallest number that has not been viewed in the list is 997, which is naturally the 168th simplest.

This needs to be done only 168 times, because all numbers can be expressed as the product of a list of primes, and the number is less than 1,000,000, which is a multiple of the number 169 of the number (1,009), which is NOT a multiple of the number below 1009. The smallest number that would be removed by sieving 1009, which has not yet been removed, is 1009 * 1013 = 1,022,117 , or the 169th stroke times the 170th number, which clearly exceeds 100,000, and therefore t needs to be checked for this set of numbers.

Therefore, all multiples of 1009 have already been removed from the list when you reach this point, so there is no point in continuing, since you have already deleted all non-prime numbers from the list .: D

Answer 2

There are 168 primes less than 1000.

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