## Prime Numbers: Finding the first N Primes – Part 4 Sieve of Eratosthenes and Erdos Prime Number Theorm

Posted by tekpool on October 6, 2006

**Q: Finding the first N Primes
Part 4 Sieve of Eratosthenes and Erdos Prime Number Theorm**

We have been using regular Computer Science procedures for improving efficiency here. It’s time to borrow some good old Math theorms now. The first of the techniques, that I am going to use is the Sieve of Eratosthenes

This is an algorithm for making tables of primes. Sequentially write down the integers from 2 to the highest number you wish to include in the table. Cross out all numbers >2 which are divisible by 2 (every second number). Find the smallest remaining number >2 . It is 3. So cross out all numbers >3 which are divisible by 3 (every third number). Find the smallest remaining number >3 . It is 5. So cross out all numbers >5 which are divisible by 5 (every fifth number).

Continue until you have crossed out all numbers divisible by sqrt(n), The numbers remaining are prime.

This idea can be used easily to find all primes below a given number. But, how do you use this to find the first N primes. Here’s a quick idea, Use Erdos Prime Number Theorm. You use this to find a Cap, which is the number until which you need to check to get N primes.

```
```float FindPrimeCap(int x)
{
float flX = (float) x;
float flCap = 1.0f;
for(float f=2.0f; flCap

FindPrimeCap uses Erdos Prime Number Theorm. Since this is asymptotic, it is not accurate enough for small numbers.

However, timing this code showed that this method was faster than all of the previous method we discussed.

In fact more prime were found in lesser time, using this method compared to the previous ones.

In a later post, We will analye the performance of all the methods we have discussed so far

## Anil kumar said

Good site…just a bit unclear with codes like in this page”prime-numbers-finding-the-first-n-primes-part-4-sieve-of-eratosthenes-and-erdos-prime-number-theorm”.. plz improve this thing otherwise its good.

## 홈패션 said

May I simply sayy what a comfort to find somebody that actually knows what

they’re talking about over the internet. You certainly know how to bring a problem to light

and maske it important. More people have to check this out andd

understand this side of your story. It’s surprisimg you are

not more popular becausxe you defnitely possess the gift.