Get the square root of the number you are evaluating (for example evaluate 9), this is because if the number you are evaluating is not divisible by any number below the square root then you don't need to test every number above it). For (i = 2; i <= sqrt(number); i++) if((number/i)*i == number) return NotPrime; } return Prime This tests to see if the number can be divided by i and if it can then it is not a prime number. Once you have tested for all integers up to the square root of the number you will know if it is prime or not. For our example we used 9. First i = 2 and (9/2)*2 does not equal 9 (provided you use integers) because integers cannot be fractions you will get 8 when you try (9/2)*2. Next i = 3 and we see that (9/3)*3 == 9 and therefore 9 is not prime.