Abstract / Summary

Find all numbers up to a given limit that have exactly three positive divisors.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (200k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The Solution.isThree method determines whether a given integer n has exactly three positive divisors. Mathematically, a number possesses three divisors only when it is the square of a prime. The implementation follows this characterization step-by-step, using early exits and minimal iteration to keep the execution fast.

Key Steps

Early rejection of small inputs

if n < 4:
    return False

Numbers less than four cannot be squares of primes, because the smallest prime is 2 and (2^2 = 4). This guard eliminates trivial cases such as 0, 1, 2, and 3 without further computation.

Verification that n is a perfect square

p = int(sqrt(n))
if n != p * p:
    return False

The integer square root p is computed once. If squaring p does not reproduce n, the number cannot be a prime square, and the function returns immediately.

Prime test for the square root

The algorithm now checks whether p itself is prime.

Even-number shortcut

if p % 2 == 0:
    return p == 2

If p is even, the only possible prime is 2. This single comparison avoids entering the loop for all even candidates.

Trial division by odd numbers only

for i in range(3, int(sqrt(p)) + 1, 2):
    if p % i == 0:
        return False

The loop iterates from 3 up to the integer square root of p, stepping by 2, thereby testing only odd divisors. Any divisor found proves p composite, causing an early return.

Successful conclusion

If none of the early returns trigger, the method reaches the final line:

return True

At this point n is confirmed to be the square of a prime, guaranteeing exactly three divisors.

Edge Cases Handled

The code explicitly handles the smallest inputs (n < 4) by returning False. It also correctly processes the case where p equals 2, the only even prime, through the dedicated even-number check. When n is a perfect square of a composite number (for example, 36 = 6²), the prime test discovers a divisor of p and returns False. Non-square numbers such as 10 are rejected by the perfect-square verification step.

Performance Optimizations

The implementation minimizes work in several ways. First, the early guard for n < 4 prevents unnecessary calculations for trivial inputs. Second, computing the integer square root once and reusing it avoids repeated floating-point operations. The even-number shortcut eliminates the need for loop iteration when p is even. Finally, the trial-division loop examines only odd candidates up to √p, halving the number of iterations compared to a naïve check of every integer. These choices keep the runtime low, especially for large values of n where the square root of p is relatively small.

Think of a secret club where numbers are invited to join only if they have exactly three friends who divide them perfectly. A number divides another if it fits inside without leaving any crumbs behind. Imagine starting with the number one and ending with the number itself as two of the friends. For a number to have exactly three friends, it must be the result of a prime number multiplied by itself. A prime number is a special figure that cannot be broken into smaller equal groups.

First, the code checks if the number is too small. If the number is smaller than four, it cannot have three friends, so it skips the party. Next, the code looks for a square number, which is a number made by multiplying a starting number by itself. If the chosen number is not a perfect square, it is not invited.

After finding the starting number, the code performs one final test to see if that starting number is a prime number. It checks if the starting number can be divided by any smaller numbers. If that starting number has any other friends hidden away, it is not prime, and the original number is not allowed in the club. If the starting number stays strong and keeps to itself, the original number passes the test and belongs in the special group of numbers with exactly three friends.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: sublinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python			TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++	JS	Java		Python	Go
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem				Ruby
	fsq	C++
	JoshCrozier		JS
	lkwq007					Python
	muhammadfarhankt						Go
	suxrobGM							C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality