Technical Interview Questions

The largest pool of technical questions with answers, explantions, code and detailed analysis

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

Advertisements

2 Responses to “Prime Numbers: Finding the first N Primes – Part 4 Sieve of Eratosthenes and Erdos Prime Number Theorm”

  1. 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.

  2. 홈패션 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

 
%d bloggers like this: