Sunday, March 16, 2008

Sieve of eratosthenes algorithm perfomance

Prime numbers are very interesting for just 1 reason - they are unique in that sense that they are not divisible from any number without remainder, except 1 and itself. So there are many algorithms for finding prime numbers. But first not very complex and fast algoritm is "Sieve of eratosthenes". This algorithm pseudocode:
1. Take next number
2. Check is number X exists in composite numbers list
3.
if (2) not - it is prime number, - then add numbers X*2,X*3,X*4,...X*n (X*n- maximum number until primes will be looked) to the composite numbers list
- go to step 1
if (2) yes - it is not prime number, rather composite.
- go to step 1
4. Repeat 1-4 until the maximum number you need to search.
C# code:



static int PrimesBelow(long until)
{
int sum = 0;
bool[] composite = new bool[until + 1];
for (long i = 2; i < until; i++)
{
if (!composite[i])
{
for (long j = i + i; j <= until; j += i)
{
composite[j] = true;
}
sum++;
}
}
return sum;
}



So after executing this code to find primes with different prime search limit, we get this picture of algorithm perfomance:
_________________________
Prime count --- CPU time (ms)
78498 ________ 15
120322 _______46
184586 _______62
283551 _______93
436077 _______234
671165 _______421
1034145 ______765
1594712 ______1296
2461527 ______2140
3801997 ______3515
5876959 ______5671
9091052 ______9218
14073059 _____15109
21798316 _____24671
33785616 _____40781
________________________

So we see that for example 9 million first prime numbers will be found in just 9 seconds.
Also we see that running time almost linear, that is time depends on prime search space linearly.

Conclusion:
IMHO if you want fast, not very complex algorithm for finding prime numbers- I would suggest this algorithm - "Sieve of eratosthenes". But of course this algorithm is not suitable if you want search big prime numbers, because of it requirements on memory consumption. When array gets out of RAM, this algorithm is not effective anymore...
But in any way this algorithm is old but still good, at least comparing with trivial trial division algorithm...

No comments:

Post a Comment

Comment will be posted after comment moderation.
Thank you for your appreciation.