4

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();
Matt Ellen
  • 11,268
  • 4
  • 68
  • 90
Dan
  • 257
  • 1
  • 3
  • 11
  • 1
    This is **not a Sieve of Eratosthenes**, which would only use additions to cull composite numbers from an array; **it is a Trial Division Prime Sieve** as it eliminates composite numbers over a range by trial division and testing for non zero remainders. It is a kind of optimized version because it only divides by found primes. It isn't an exact optimization because it requires an estimate of at least the number of primes up to the square root of the range (as 168 is the number of primes to 1000 for range 1000000). A better version is [here](http://stackoverflow.com/a/1510186/549617). – GordonBGood Apr 30 '14 at 07:41

2 Answers2

3

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

Gordon Gustafson
  • 40,133
  • 25
  • 115
  • 157
  • How do we generalize this code to find out all primes less than n? What will be the value of 168 in that case? – Raj Jul 25 '13 at 23:22
  • 1
    @Raj Replace `1000000` with `n`, and replace 168 with [the prime counting function](http://www.wikipedia.org/wiki/Prime-counting_function) evaluated at `sqrt(n)`. TLDR: For `x>=17`, `1.25506 * x/(log(x))` will be greater than the prime counting function, so you can just use that (with `x = sqrt(n)` of course). – Gordon Gustafson Jul 26 '13 at 02:29
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.

Elian Ebbing
  • 18,779
  • 5
  • 48
  • 56