A prime tester is a basic algorithm that can be enhanced, and let's the interviewer know how you think. For example testing can the input be divided evenly by every number up to itself it the most basic format. You can exploit the symmetry of multiplication and make this better by only checking numbers up to the square root of the input. Every non prime has prime factors so if you are testing numbers in sequence its quicker again to only test with prime numbers up to the square root of the input. This leads to offsetting computation, and using the space time tradeoff, you can generate a boolean map of primes using one of the various sieves and then test primes in constant time at the cost of generating all the primes beforehand. I imagine for a company like Google, optimising the algorithm for the given situation is essential. So although the question might seem basic at first the best questions have multiple solutions.