Technical Interview Questions

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

Prime Numbers: Finding the first N Primes – Part 3 Prime Divisors

Posted by tekpool on October 4, 2006

Q: Finding the first N Primes

In the last post we looked into making some improvements over Trivial Approaches

Lets look at ways into how we can make this faster. The improvements made in the last post where basically about skipping everyone second and third number, and not skipping divisors that are multiples of 2 and 3. This holds true, because, if the number were a multiple of 2 or 3, it would be dealt with in the first place, where we skipped all numbers that were multiples of 2’s and 3’s. Now this idea can be extended to number upto 5, 7, 11 and so one. The general way to do this will be to store the primes already found and only use these primes are divisors.

void GetPrimesPrimeDivisiors(int n) 
    int* prime = new int[n]; 
    int count=1; 
    int j=3; 


Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: