Three Divisors - Leetcode Solution

Problem:

Given an integer n, decide if n has a third divisor other than 1 and n.

If you are given an integer n, you are supposed to find out if the integer has 3 divisors, excluding 1 and the integer n itself.

Example 1:

Input: n = 2 Output: false Explanation: There are only two divisors: 1 and 2.

Example 2:

Input: n = 4 Output: true Explanation: The divisors are 1,2,4.

Solution:

The brute-force idea is to start from 2 and check all the numbers in the range of [2,sqrt(n)], whether they are the divisors of n. If there are 3 divisors, return true. Otherwise, return false. The time complexity is O(sqrt(n)).

Here is the code to check whether the integer n has a third divisor other than 1 and n.

class Solution {
public:
    bool isThree(int n) {
        if (n == 1)
            return false;
        int cnt = 1;
        for (int i = 2; i <= sqrt(n); i++) {
            if (n % i == 0) {
                cnt++;
                if (i != n / i)
                    cnt++;
                if (cnt > 2)
                    break;
            }
        }
        return cnt == 2;
    }
};

Explanation:

In this code, if n is equal to 1, the function will return false since 1 only has two divisors 1 and itself.

The variable cnt is used to record the number of divisors. We start from 2 and check all the numbers in the range of [2,sqrt(n)], whether they are the divisors of n. If i is a divisor of n and n/i is also a divisor of n, we add 2 into cnt. If i is a divisor of n and n/i is not i, we add 1 into cnt. When cnt is greater than 2, we break the loop.

Finally, we return true if cnt is equal to 2, which means that there are exactly 3 divisors excluding 1 and the integer n itself.

Time Complexity:

The time complexity of this solution is O(sqrt(n)) because we only need to check all the numbers in the range of [2,sqrt(n)].

1