Interview Question

Software Engineer Interview Westford, MA

Create an algorithm that tests to see if a number is prime


Interview Answer

3 Answers


Run a loop to devide number by all the numbers starting from one to the one less number that the Prime number itself and check for remainder. If the remainder is same as the number itself than its prime number.

for example, say number 17. Run a loop from 1 to 16. On each loop instance, divide 17 with the loop counter number (1..2......16 etc) and check for remainder. None of these number will give you any other remainder than 17 because 17 is a Prime number. Check the logic yourself with 1, 3, 7, 13, 17,19, ....

Hope it helps! Please, reply if someone finds any logical errors in it.

Bhavin Mehta on Jun 25, 2009

Well, if a number cannot be divided by 2, then there is no way it can be divided by 4, by 6, by 8, ... So it is overkill to test all the even numbers!

Also if n is our number, you don't need to go from 2 to n, from 2 to sqrt(n) will do the job

Eric Pruneau on Mar 7, 2010

A number is prime if it's divisible by 1 and itself. We know that every number is divisible by itself so you need a loop to go from 1-n/2. That means 7 is not divisible by 4,5,6.

int j=0;

for (int i=1;i<=n/2;i++)
if (j==1)
return prime;
return not prime;

JP on Aug 4, 2010

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up