# Three Divisors
**Difficulty:** EASY
[External](https://leetcode.com/problems/three-divisors)
Canonical: https://scaleengineer.com/dsa/problems/three-divisors
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
---
## Problem
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`

# Approaches
## Brute Force Divisor Counting
This approach directly implements the definition of a divisor. We iterate through all numbers from 1 to `n` and count how many of them divide `n` evenly. If the final count is exactly 3, we return `true`; otherwise, we return `false`.
**Time:** `O(n)` - The loop runs `n` times, making the time complexity linear with respect to the input `n`. · **Space:** `O(1)` - We only use a constant amount of extra space for the counter variable.
**Pros:** Very simple to understand and implement directly from the problem definition.
**Cons:** Inefficient for large values of `n` due to the linear time complexity. It will be too slow if `n` is large, though it passes for the given constraints (`n <= 10^4`).
### Explanation
The algorithm starts by initializing a counter for divisors to zero. A small optimization is to note that the smallest number with three divisors is 4, so any `n < 4` can be immediately rejected. It then enters a loop that iterates from `i = 1` up to the given number `n`. Inside the loop, it checks if `i` is a divisor of `n` using the modulo operator (`n % i == 0`). If `i` is a divisor, the counter is incremented. After the loop completes, the algorithm checks if the final count of divisors is equal to 3.
```java
class Solution {
    public boolean isThree(int n) {
        if (n < 4) {
            return false;
        }
        int divisors = 0;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                divisors++;
            }
        }
        return divisors == 3;
    }
}
```
### Algorithm
*   If `n < 4`, return `false`.
*   Initialize a counter `divisors` to 0.
*   Iterate with a variable `i` from 1 to `n`.
*   In each iteration, check if `n` is divisible by `i`.
*   If `n % i == 0`, increment `divisors`.
*   After the loop, return `true` if `divisors` is exactly 3, otherwise return `false`.

## Optimized Divisor Counting up to Square Root
This approach improves upon the brute-force method by recognizing that divisors come in pairs. If `i` is a divisor of `n`, then `n/i` is also a divisor. We only need to iterate up to the square root of `n` to find all divisors, which is much more efficient.
**Time:** `O(sqrt(n))` - The loop runs up to the square root of `n`, which is a significant improvement over the linear scan. · **Space:** `O(1)` - We only use a constant amount of extra space.
**Pros:** Much faster than the O(n) approach.; Still relatively easy to understand.
**Cons:** While efficient, it's not the most optimal solution as it doesn't use the core mathematical property of such numbers.
### Explanation
The algorithm iterates from `i = 1` up to `sqrt(n)`. For each `i` that divides `n`, we have found a pair of divisors: `i` and `n/i`.
If `i * i == n`, then `i` and `n/i` are the same (i.e., `n` is a perfect square), so we've found only one unique divisor. We increment our divisor count by one.
If `i * i != n`, we have found two distinct divisors, `i` and `n/i`. We increment our count by two.
After the loop, we check if the total count is 3.
```java
class Solution {
    public boolean isThree(int n) {
        // Smallest number with 3 divisors is 4.
        if (n < 4) {
            return false;
        }
        int count = 0;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                // i is a divisor.
                // n/i is also a divisor.
                if (i * i == n) {
                    // If i is the square root, we count it once.
                    count++;
                } else {
                    // Otherwise, we count both i and n/i.
                    count += 2;
                }
            }
        }
        return count == 3;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Iterate with a variable `i` from 1 up to `floor(sqrt(n))`.
*   In each iteration, check if `n` is divisible by `i`.
*   If `n % i == 0`:
    *   If `i * i == n`, it means `i` is the square root, so we increment `count` by 1.
    *   Otherwise, `i` and `n/i` are a pair of distinct divisors, so we increment `count` by 2.
*   After the loop, return `true` if `count` is exactly 3, otherwise return `false`.

## Mathematical Approach: Perfect Square of a Prime
The most efficient approach relies on a key mathematical insight. A number has exactly three positive divisors if and only if it is the square of a prime number. For a prime number `p`, the divisors of `p^2` are `1`, `p`, and `p^2`. This transforms the problem from counting divisors to checking for this specific property.
**Time:** `O(n^(1/4))` - Calculating `sqrt(n)` is fast. The primality test for `root = sqrt(n)` takes `O(sqrt(root))` time, which is `O(sqrt(sqrt(n)))` or `O(n^(1/4))`. This is the fastest approach. · **Space:** `O(1)` - No extra space proportional to the input size is used.
**Pros:** The most efficient algorithm due to its strong mathematical foundation.; Scales very well for much larger values of `n`.
**Cons:** Requires understanding the number theory behind the problem, making it slightly less intuitive than direct counting methods.
### Explanation
The algorithm first checks if `n` is a perfect square. We can do this by calculating its integer square root, let's call it `root`, and then checking if `root * root` equals `n`. If `n` is not a perfect square, it cannot have an odd number of divisors, and thus cannot have exactly three. In this case, we return `false`. If `n` is a perfect square, we then need to determine if its square root, `root`, is a prime number. We can use a standard primality test for `root`. A number `p` is prime if it's greater than 1 and has no divisors other than 1 and itself. We can check for divisibility from 2 up to `sqrt(p)`. If `root` is prime, then `n` has exactly three divisors.
```java
class Solution {
    public boolean isThree(int n) {
        // A number n has exactly three divisors if it is a square of a prime number.
        // Smallest such number is 2*2=4.
        if (n < 4) {
            return false;
        }
        
        int root = (int) Math.sqrt(n);
        
        // Check if n is a perfect square.
        if (root * root != n) {
            return false;
        }
        
        // If it is a perfect square, check if its root is prime.
        return isPrime(root);
    }

    private boolean isPrime(int num) {
        // 1 is not a prime number.
        if (num <= 1) {
            return false;
        }
        // Check for factors from 2 up to sqrt(num).
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false; // Found a factor, so not prime.
            }
        }
        return true; // No factors found, so it's prime.
    }
}
```
### Algorithm
*   Handle the base case: if `n < 4`, return `false`.
*   Calculate the integer square root of `n`, let's call it `root`.
*   Check if `n` is a perfect square by verifying if `root * root == n`. If not, return `false`.
*   If `n` is a perfect square, check if `root` is a prime number using a helper function.
*   The `isPrime` helper function checks if a number `p` is prime:
    *   Return `false` if `p <= 1`.
    *   Iterate from 2 up to `sqrt(p)`. If any number in this range divides `p`, return `false`.
    *   If the loop completes, return `true`.
*   Return the result of the primality test on `root`.

# Solutions
### Java

```java
class Solution {
public
  boolean isThree(int n) {
    int cnt = 0;
    for (int i = 2; i < n; i++) {
      if (n % i == 0) {
        ++cnt;
      }
    }
    return cnt == 1;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @return {boolean} */ var isThree = function (n) {
  let cnt = 0;
  for (let i = 2; i < n; ++i) {
    if (n % i == 0) {
      ++cnt;
    }
  }
  return cnt == 1;
};

```

### CPP

```cpp
class Solution {
public:
  bool isThree(int n) {
    int cnt = 0;
    for (int i = 2; i < n; ++i) {
      cnt += n % i == 0;
    }
    return cnt == 1;
  }
};

```

### Python

```python
class Solution:
    def isThree(self, n: int) -> bool: return sum(n %
                                                  i == 0 for i in range(2, n)) == 1

```