Three Divisors: Spotting Squares of Primes

LeetCode 1952. Three Divisors gives you a positive integer n and asks whether it has exactly three positive divisors. At first glance you might think you need to loop through every number up to n and count, but a bit of number theory turns this into a two-step check.

The problem

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

• n = 2 returns false (divisors: 1, 2)
• n = 4 returns true (divisors: 1, 2, 4)
• n = 12 returns false (divisors: 1, 2, 3, 4, 6, 12)

The approach

Think about what it means for a number to have exactly three divisors. Every positive integer has 1 and itself as divisors. So for there to be exactly three, there must be precisely one more divisor sitting between 1 and n.

If n = p^2 for some prime p, the divisors are exactly 1, p, and p^2. That gives three. Conversely, if n is not a perfect square, its divisors come in pairs (for every divisor d, the number n/d is also a divisor and d != n/d). So the divisor count would be even, never three. And if n is the square of a composite number, the root's own factors produce extra divisors of n.

The conclusion: n has exactly three divisors if and only if n is the square of a prime number.

The algorithm becomes:

1. Check if n is a perfect square.
2. If yes, check if sqrt(n) is prime.
3. Return the result.

Visual walkthrough

Each example confirms the pattern. Non-squares fail immediately. Squares of primes pass. Squares of composites (like 16 = 4^2, where 4 is not prime) would fail the primality check.

The code

import math

def isThree(n: int) -> bool:
    root = int(math.isqrt(n))
    if root * root != n:
        return False
    if root < 2:
        return False
    for i in range(2, int(math.isqrt(root)) + 1):
        if root % i == 0:
            return False
    return True

The function starts by computing the integer square root of n. If root * root != n, then n is not a perfect square and we return False right away. Next we handle the edge case where the root is less than 2 (since 1 is not prime). Then we check if root is prime using trial division up to sqrt(root). If any number divides it evenly, the root is composite and we return False. Otherwise we return True.

You could also solve this with a brute-force divisor count:

def isThree(n: int) -> bool:
    count = 0
    for i in range(1, n + 1):
        if n % i == 0:
            count += 1
    return count == 3

This works, but it runs in O(n) time. The prime-square approach above runs in O(sqrt(sqrt(n))), which is dramatically faster for large inputs. Both solutions pass on LeetCode, but understanding why the prime-square insight works is the real takeaway.

Complexity analysis

Computing math.isqrt(n) takes O(sqrt(n)) in the worst case. The primality check on the root iterates up to sqrt(root), which is n^(1/4). So overall time is dominated by the square root computation. Space is constant since we only use a few variables.

Building blocks

1. Perfect square detection

Check whether a number is a perfect square by computing the integer square root and squaring it back. This pattern appears in problems like "Valid Perfect Square" and any time you need to reason about factor pairs.

root = int(math.isqrt(n))
is_square = root * root == n

2. Primality testing by trial division

Test whether a number is prime by checking divisibility from 2 up to its square root. This is one of the most fundamental building blocks in number theory problems.

def is_prime(x):
    if x < 2:
        return False
    for i in range(2, int(math.isqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

3. Divisor counting

Count divisors by iterating up to sqrt(n) and counting pairs. Useful when you need the full divisor count rather than just checking for exactly three.

def count_divisors(n):
    count = 0
    for i in range(1, int(math.isqrt(n)) + 1):
        if n % i == 0:
            count += 2 if i != n // i else 1
    return count

Edge cases

• n = 1: Only one divisor (1 itself). Returns false.
• n = 2: Two divisors (1 and 2). Returns false. The smallest prime squared is 4.
• n = 4: The smallest number with exactly three divisors. sqrt(4) = 2, which is prime.
• Large prime squared (e.g., n = 961 = 31^2): The primality check on 31 runs quickly. Still returns true.

From understanding to recall

You can read this solution and understand why squares of primes have exactly three divisors. But will you remember the insight when you see a divisor-counting problem in an interview two weeks from now? The connection between "three divisors" and "square of a prime" is the kind of mathematical shortcut that fades without reinforcement.

CodeBricks drills each building block separately. You practice perfect square detection in one session, primality testing in another, and divisor counting in a third. When they show up combined in a problem like Three Divisors, you recognize all the pieces and snap them together without hesitation.

Related posts

• Happy Number - Math-based digit manipulation with cycle detection
• Add Digits - Number theory insight that simplifies the algorithm
• Factorial Trailing Zeroes - Counting factors with mathematical patterns