techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

prime numbers

Given a number, describe an efficient algorithm to find the next number which is prime.
codeislife
Sunday, March 12, 2006
 
 
This is not a simple easy question.
Take a look at http://en.wikipedia.org/wiki/Prime_testing
Abdel Said Send private email
Sunday, March 12, 2006
 
 
This might work. Note: This is not the whole program.

Int number_entered; //Number entered by the user.
Int next_prime = number_entered;
Int is_prime = 0;
Int divisor;

While (is_prime == 0 , next_prime++)
  For (divisor = 2; divisor <= next_prime; divisor++)
      If (next_prime mod divisor == 0){
        If (next_prime == divisor)
            is_prime = 1;
        break;
      }

 

println(“\n\nNext prime: %d”, &next_prime);
Will Send private email
Wednesday, March 15, 2006
 
 
You may save some time by only checking odd numbers and in the for loop only dividing by odd numbers.
Radu Cornea Send private email
Thursday, March 16, 2006
 
 
You might save time by comparing only odd number, but '4' would be returned as prime.  You DO want to stop your checking at the square root of the number entered.
Brian Czako Send private email
Friday, March 17, 2006
 
 
You obviously have to take care of 2, which is the only even prime number. Other than that you can safely go with only odd numbers and '4' will not be among these.
Radu Cornea Send private email
Friday, March 17, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz