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.