15,565,403 members
Articles / Programming Languages / C#
Alternative
Tip/Trick
Posted 28 Sep 2011

13.6K views
1 bookmarked

Find Prime Numbers in C# Using the Sieve of Eratosthenes

Rate me:
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 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++;
}

}
}
```

Written By
Web Developer
United States
Developer