Click here to Skip to main content
15,565,403 members
Articles / Programming Languages / C#
Alternative
Tip/Trick
Posted 28 Sep 2011

Tagged as

Stats

13.6K views
1 bookmarked

Find Prime Numbers in C# Using the Sieve of Eratosthenes

Rate me:
Please Sign up or sign in to vote.
5.00/5 (3 votes)
30 Sep 2011CPOL
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...
Hi,

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

C#
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 
ResultsAlt #1Alt #4Primes
200,0006.06.017,984
2,000,00054.047.0148,933
20,000,000550.0447.01,270,607
200,000,0006955.06025.011,078,937
2,000,000,00078,994.067,285.098,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;
     }
 }

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Web Developer
United States United States
Developer

Comments and Discussions

 
SuggestionArgumentOutOfRangeException Pin
david groenewald24-Apr-12 11:45
david groenewald24-Apr-12 11:45 
GeneralReason for my vote of 5 For that fascinating link to "Prime ... Pin
Qwertie12-Oct-11 12:17
Qwertie12-Oct-11 12:17 
GeneralI learned this method in my algebra class in high school and... Pin
Dave Vroman11-Oct-11 20:33
professionalDave Vroman11-Oct-11 20:33 
GeneralReason for my vote of 5 This is the mathematicians way of so... Pin
Dave Vroman11-Oct-11 20:31
professionalDave Vroman11-Oct-11 20:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.