Three Divisors

LeetCode 2083 | Difficulty: Easy

Easy

Problem Description

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 <= 10^4`

Topics: Math, Enumeration, Number Theory

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 44 ms)

Metric	Value
Runtime	44 ms
Memory	15.2 MB
Date	2021-08-23

Solution

public class Solution {
    public bool IsThree(int n) {
        if(n<4) return false;
    int count = 1;
    for (int i = 2; i <= n/2; i++)
    {
        if(n%i == 0)
        {
            count++;
            if(count>3) return false;
        }
    }
    count++;
    return count == 3;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: You can count the number of divisors and just check that they are 3

Hint 2: Beware of the case of n equal 1 as some solutions might fail in it