Technical Interview Questions

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

Prime Numbers: Finding the first N Primes – Part 1 Trivial Approaches

Posted by tekpool on October 2, 2006

Q: Finding whether or not a number is prime?

Sol: There are several ways to solve this problem. Lets look into some of the more trivial approaches as usual and try to improve on these as we move along.

By Definition, a prime number is a positive integer having exactly one positive divisor other than 1. Therefore the straightforward way to do this will be to check divisibility of the given number starting from 2 to the given number.

There are some easy ways to improve upon this basic approach.

  1. You do not have to check for all numbers upto n. Some would argue that checking upto n/2 would suffice, since anything greater than this will not divide the given number as a whole number
  2. Actually, you will not even need to go upto n/2. Checking upto sqrt(n) would suffice. This is because anything if there was a number greater than this that would actuall divide the divide the given number, you would have already visited the factor since that number will be less than or equal to sqrt(n). E.g If 91 was the given number, you would not have to check for numbers greater than 9. This is beacause although 13 divides 91, this would already have been found since you would have checked 7 prior to this and this is less that 9 (floor(sqrt(91))

void GetPrimes(int n) 
{ 
    // Start from 3 
    int j=3; 
    // There is already one prime (2), so set count=1 
    int count = 1; 
    while(count

Advertisements

4 Responses to “Prime Numbers: Finding the first N Primes – Part 1 Trivial Approaches”

  1. logan said

    The code is not complete?? Can you please correct this?

    Between, this is an excellent site! Great work, God bless you!

  2. My fellow on Orkut shared this link and I’m not dissapointed at all that I came to your blog.

  3. roddy said

    actually if you look it up you only need to check primes up to sqrt(n)

  4. akanksha said

    pls complete this code

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 )

Connecting to %s

 
%d bloggers like this: