1952. Three Divisors

1952. Three Divisors (Easy)

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m is a divisor of n if there exists an integer k such that n = k * m.

 

Example 1:

Input: n = 2
Output: false
Explantion: 2 has only two divisors: 1 and 2.

Example 2:

Input: n = 4
Output: true
Explantion: 4 has three divisors: 1, 2, and 4.

 

Constraints:

• 1 <= n <= 104

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/three-divisors/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool isThree(int n) {
        int ans = 0;
        for (int i = 1; i <= n && ans <= 3; ++i) {
            if (n % i == 0) ++ans;
        }
        return ans == 3;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/three-divisors/
// Author: github.com/lzl124631x
// Time: O(sqrt(N))
// Space: O(1)
class Solution {
public:
    bool isThree(int n) {
        int ans = 0;
        for (int i = 1; i * i <= n && ans <= 3; ++i) {
            if (n % i == 0) {
                ++ans;
                if (n / i != i) ++ans;
            }
        }
        return ans == 3;
    }
};