Three Divisors

Three Divisors

What is this problem about?

In number theory, every positive integer has a set of divisors. "Three Divisors" asks you to determine if a given positive integer 'n' has exactly three positive divisors. If it does, return true; otherwise, return false. This problem requires an understanding of how the number of divisors relates to the prime factorization of a number.

Why is this asked in interviews?

This three divisors interview question is a classic math-based problem used by Microsoft and Google. It tests your ability to apply mathematical properties to simplify a search. While you could check every number from 1 to 'n' to count its divisors, an efficient solution requires recognizing the specific mathematical property of numbers with exactly three divisors: they are always squares of prime numbers.

Algorithmic pattern used

This problem follows the Math, Number Theory, Enumeration interview pattern.

1. A number has exactly 3 divisors if and only if it is the square of a prime number. For example, 4 = 2^2 (divisors: 1, 2, 4); 9 = 3^2 (divisors: 1, 3, 9); 25 = 5^2 (divisors: 1, 5, 25).
2. To check this:
   • Calculate the integer square root of 'n'.
   • Check if sqrt * sqrt == n.
   • If it is, check if sqrt is a prime number.
3. To check if sqrt is prime:
   • If sqrt < 2, return false.
   • Iterate from 2 to the square root of sqrt. If any number divides sqrt, it's not prime.

Example explanation

n = 9.

1. sqrt(9) = 3. 3 * 3 is 9.
2. Is 3 prime? Yes. Result: True. n = 15.
3. sqrt(15) is not an integer (3.87). Result: False. n = 49.
4. sqrt(49) = 7. 7 * 7 is 49.
5. Is 7 prime? Yes. Result: True.

Common mistakes candidates make

In "Three Divisors coding problem," a common mistake is only checking if the number is a perfect square. For example, 16 is a perfect square (4^2), but its divisors are 1, 2, 4, 8, 16 (total of 5). The square root must be prime. Another error is not correctly handling the case where n=1 (divisors: {1}, total 1).

Interview preparation tip

Brush up on basic prime properties. Knowing that the number of divisors is determined by the exponents in the prime factorization ( (e1+1)(e2+1)... ) is very helpful. For a number to have exactly 3 divisors, there must be only one prime factor with an exponent of 2.