Three Divisors

Easy
545.

Three Divisors

Three Divisors is an easy coding problem on math and number theory, asked in Amazon and TCS interviews.

Given an integer n, return true if it has exactly three positive divisors, and false otherwise.

Example 1

Input
n = 2
Output
false
Explanation
Its divisors are 1 and 2.

Example 2

Input
n = 4
Output
true
Explanation
Its divisors are 1, 2 and 4.

Example 3

Input
n = 9
Output
true

Constraints

  • 1 <= n <= 10000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {boolean}
 */
var isThree = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Three Divisors — Solution in Python, Java & C++

Three Divisors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and TCS.

Three Divisors is an easy coding problem on math and number theory, asked in Amazon and TCS interviews.

  • Difficulty: Easy
  • Topics: Math, Number Theory
  • Asked at: Amazon, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer n, return true if it has exactly three positive divisors, and false otherwise.

Example 1

Input: n = 2
Output: false
Explanation: Its divisors are 1 and 2.

Example 2

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

Example 3

Input: n = 9
Output: true

Constraints

  • 1 <= n <= 10000

Hints for Three Divisors

  1. Hint 1

    Counting divisors up to sqrt(n) is enough — divisors come in pairs.

  2. Hint 2

    Remember that a perfect square's square root pairs with itself and must be counted once.

  3. Hint 3

    Which numbers have exactly three divisors? Look at the answer's shape.

How to solve Three Divisors

Divisors pair up as d and n/d, so counting up to sqrt(n) covers them all. The characterisation, if you want it: exactly the squares of primes have three divisors.

Approach

  1. Loop d from 1 while d * d <= n.
  2. When d divides n, add 2 to the count — or 1 when d * d == n, since the pair collapses.
  3. Bail out early once the count exceeds 3.
  4. Return whether the final count is exactly 3.

Why it works

n = p² for prime p has divisors 1, p, p² — exactly three. Any other form has either fewer (1 or a prime) or more (a composite with two distinct prime factors, or a higher prime power).

Complexity

  • Time — O(sqrt(n))
  • Space — O(1)

Pitfalls

  • Double-counting the square root turns 4 and 9 into four-divisor numbers.
  • Looping all the way to n is 10,000 iterations here — fine, but the sqrt bound is the right habit.
  • n = 1 has a single divisor and must return false.

Reference solution

Python

def isThree(n: int) -> bool:
    count = 0
    d = 1
    while d * d <= n:
        if n % d == 0:
            count += 1 if d * d == n else 2
            if count > 3:
                return False
        d += 1
    return count == 3

Java

public static boolean isThree(int n) {
    int count = 0;
    for (int d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            count += d * d == n ? 1 : 2;
            if (count > 3) return false;
        }
    }
    return count == 3;
}

C++

bool isThree(int n) {
    int count = 0;
    for (int d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            count += d * d == n ? 1 : 2;
            if (count > 3) return false;
        }
    }
    return count == 3;
}

JavaScript

var isThree = function(n) {
    let count = 0;
    for (let d = 1; d * d <= n; d++) {
        if (n % d === 0) {
            count += d * d === n ? 1 : 2;
            if (count > 3) return false;
        }
    }
    return count === 3;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue