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 |
public static int Sieve(int candidate)
{
var sieveContainer = new BitArray(candidate + 1, false);
sieveContainer.Set(2, true);
sieveContainer.Set(3, true);
for (int i = 6; i <= candidate; i += 6)
{
sieveContainer.Set(i+1, true);
sieveContainer.Set(i-1, true);
}
long marker, factor;
marker = 5;
while (marker * 2 <= candidate)
{
while (marker * marker <= candidate)
{
sieveContainer.Set((int)(marker * marker), false);
break;
}
factor = (marker * marker) + (marker * 6);
while (factor <= candidate)
{
sieveContainer.Set((int)factor, false);
factor += 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;
}
}