Find Prime Numbers in C# Using the Sieve of Eratosthenes

Hi,

Thanks for the feedback for alternative #1 from above (and thank you, Jurgen Rohr for your suggestion! I replaced the "reset" line with:

while (!sieveContainer.Get(++marker));
factor = marker;

Here is another algorithm that's slightly different. It's not as elegant an approach, but appears to run quickly and I thought it was interesting to view the sieving container this way. While testing on my machine comparing alternative #1 from above to this one, I can get both to run about the same, with a slight edge to this new solution for bigger candidate values. Running for candidate = 10^7 ~ 850 milliseconds; 10^8 ~ 10seconds; 10^9 ~ 115 seconds (50 million + primes).

Does anyone see ways in which this can be improved? Thanks for your feedback! (and sorry for any typos).

Update: Ok, I was able to run this on a pretty ok machine. Here are the results I found.

	Time in Milliseconds
Results	Alt #1	Alt #4	Primes
200,000	6.0	6.0	17,984
2,000,000	54.0	47.0	148,933
20,000,000	550.0	447.0	1,270,607
200,000,000	6955.0	6025.0	11,078,937
2,000,000,000	78,994.0	67,285.0	98,222,287

//The idea is to narrow the sievingContainer to only look at 1/3 of the numbers.
     //(knot theory, http://www.scribd.com/doc/9935691/Prime-Numbers-without-Mystery-2
     //Below are 6 columns of numbers. You can see columns 1 (1,7,13,..) and column 5 (5,11,17, ...)
     //Everything in column 2-4,6 can be ignored.
     //Primes are only in columns 1 and 5 (along with prime factors of only 2 primes and primes squared).
     //ie: 25 (5^2), 35 (7*5), 65 (5*13), 49, 91 (7 * 13)
     /*
         1   2   3   4   5   6
         7   8   9   10  11  12
         13  14  15  16  17  18
         19  20  21  22  23  24
         25  26  27  28  29  30
         31  32  33  34  35  36
         37  38  39  40  41  42
         43  44  45  46  47  48
         49  50  51  52  53  54
         55  56  57  58  59  60
         61  62  63  64  65  66
         67  68  69  70  71  72
         73  74  75  76  77  78
         79  80  81  82  83  84
         85  86  87  88  89  90
         91  92  93  94  95  96
         97  98  99  100 101 102
         103 104 105 106 107 108
         ....
     */
     public static int Sieve(int candidate)
     {
         var sieveContainer = new BitArray(candidate + 1, false);

         sieveContainer.Set(2, true);
         sieveContainer.Set(3, true);

         //flag all factors of 6+/-1 as prime.
         //this initializes our bit array that will be sieved.
         for (int i = 6; i <= candidate; i += 6)
         {
             sieveContainer.Set(i+1, true);
             sieveContainer.Set(i-1, true);
         }


         //Starting at marker (ie: 5), square it and flag that as not prime.
         //Then add marker * 6 to marker starting at marker^2. (ie: 5 * 5 = 25, add 5*6 = 30, so 30+25=55, 85,...). Flag those as not prime
         //Next, add marker * 6 to marker starting at marker. (ie: 5 * 6 + 5 = 35, 65, 95. Flag these as not prime
         //Repeat starting with the next marker not sieved off. ie: 7, 11, 13
         long marker, factor;
         marker = 5;
         while (marker * 2 <= candidate)
         {
             //sieve the prime^2
             while (marker * marker <= candidate)
             {
                 sieveContainer.Set((int)(marker * marker), false);
                 break;
             }

             //sieve marker plus factors of marker * 6, starting at p^2
             factor = (marker * marker) + (marker * 6);
             while (factor <= candidate)
             {
                 sieveContainer.Set((int)factor, false);
                 factor += marker * 6;
             }

             //sieve marker plus factors of marker * 6
             factor = marker * 6 + marker;
             while (factor <= candidate)
             {
                 sieveContainer.Set((int)factor, false);
                 factor += marker * 6;
             }

             while (!sieveContainer.Get((int)++marker)) ;
         }

         marker = 0;
         int toReturn = 0;
         while (++marker < candidate)
         {
             if (sieveContainer.Get((int)marker))
                 toReturn++;
         }

         return toReturn;
     }
 }