Introduction

Numbers with exactly three positive divisors have a very specific structure. Once you know that structure, you can stop checking divisors one number at a time and replace a slow brute-force search with a much faster prime-based solution.

The Key Number Theory Fact

A number has exactly three divisors if and only if it is the square of a prime.

Why? If n = p^2 and p is prime, then the divisors are:

• '1'
• 'p'
• 'p^2'

There are exactly three.

If a number is not the square of a prime, it cannot have exactly three divisors. For example:

• '16 = 4^2, but 4 is not prime, and 16 has more than three divisors'
• '18 is not a square, so its divisors come in more complicated factor pairs'

That observation turns the problem from "count divisors for every number" into "find primes, then square them."

Brute Force Versus Better Approach

A naive algorithm checks every number and counts its divisors:

1def has_exactly_three_divisors(n):
2    count = 0
3    for d in range(1, n + 1):
4        if n % d == 0:
5            count += 1
6    return count == 3

This is correct but extremely inefficient.

A better approach is:

1. generate primes up to sqrt(limit)
2. square each prime
3. keep the squares that are within the range

Efficient Solution With a Sieve

1import math
2
3
4def primes_up_to(n):
5    if n < 2:
6        return []
7
8    sieve = [True] * (n + 1)
9    sieve[0] = sieve[1] = False
10
11    for p in range(2, int(math.isqrt(n)) + 1):
12        if sieve[p]:
13            for multiple in range(p * p, n + 1, p):
14                sieve[multiple] = False
15
16    return [i for i, is_prime in enumerate(sieve) if is_prime]
17
18
19def numbers_with_exactly_three_divisors(limit):
20    root = math.isqrt(limit)
21    return [p * p for p in primes_up_to(root)]
22
23
24print(numbers_with_exactly_three_divisors(100))

Output:

[4, 9, 25, 49]

Those are exactly the numbers up to 100 with three divisors.

Counting Instead of Listing

Sometimes the problem asks only for the count. Then you do not even need to build the squares explicitly. You only need the number of primes less than or equal to sqrt(limit):

1def count_numbers_with_exactly_three_divisors(limit):
2    return len(primes_up_to(math.isqrt(limit)))
3
4
5print(count_numbers_with_exactly_three_divisors(100))

This is especially useful when the range is large and you only care about the answer size.

Querying a Single Number

If the question is "does this one number have exactly three divisors?", use the same theorem:

1def is_prime(n):
2    if n < 2:
3        return False
4    for d in range(2, int(math.isqrt(n)) + 1):
5        if n % d == 0:
6            return False
7    return True
8
9
10def has_three_divisors(n):
11    root = math.isqrt(n)
12    return root * root == n and is_prime(root)
13
14
15print(has_three_divisors(49))
16print(has_three_divisors(48))

This is much faster than counting all divisors of n.

Why This Is Better

The improvement comes from using structure. Instead of examining every possible divisor for every number, you reduce the problem to primality.

That gives you:

• simpler reasoning
• better performance
• a solution that scales cleanly

This is a good example of how number theory often replaces brute force with one strong observation.

Common Pitfalls

The most common mistake is forgetting the "prime" part and assuming every perfect square has exactly three divisors. Only squares of primes qualify.

Another mistake is using floating-point square roots for large values and then trusting equality checks. Integer square root functions are safer.

A third issue is writing a divisor-counting loop that is technically correct but far too slow for large input sizes.

Summary

• A number has exactly three divisors if and only if it is the square of a prime.
• That fact lets you avoid brute-force divisor counting.
• For ranges, generate primes up to sqrt(limit) and square them.
• For a single number, check whether it is a perfect square whose root is prime.
• The efficient solution comes from number theory, not from micro-optimizing the brute-force loop.