Perfect Number: Divisor Sum with Square Root Optimization

LeetCode 507. Perfect Number asks you to determine whether a given integer is a perfect number. A perfect number equals the sum of all its positive divisors excluding itself. This is a classic number theory question that becomes efficient once you recognize that divisors come in pairs.

The problem

Given a positive integer num, return true if it is a perfect number and false otherwise.

A few examples:

• num = 6: divisors are 1, 2, 3. Sum = 6. Perfect.
• num = 28: divisors are 1, 2, 4, 7, 14. Sum = 28. Perfect.
• num = 12: divisors are 1, 2, 3, 4, 6. Sum = 16. Not perfect (16 is not 12).

There are only a handful of known perfect numbers: 6, 28, 496, 8128, 33550336, and so on. They get rare very quickly, but the algorithm does not rely on memorizing them.

The brute force

The most direct approach: loop from 1 to num - 1, check if each value divides num, and add it to a running total.

def check_perfect_number(num: int) -> bool:
    if num <= 1:
        return False
    total = 0
    for i in range(1, num):
        if num % i == 0:
            total += i
    return total == num

This works, but for large inputs like 100,000,000 it checks nearly a hundred million candidates. We can do much better.

The key insight

Divisors come in pairs. If i divides num, then num // i is also a divisor. For example, when num = 28 and i = 2, the pair is 14. By iterating only up to sqrt(num), you find both divisors in each pair simultaneously.

This cuts the search space from O(n) down to O(sqrt(n)).

Step-by-step walkthrough

Let's trace through num = 28 using the square root optimization.

Observations:

• We started the sum at 1 and only looped from 2 to 5 (since sqrt(28) is about 5.29).
• Each time we found a divisor i, we also grabbed its partner num // i for free.
• We checked 4 values instead of 27. For larger numbers the savings are enormous.
• The final comparison is simple: if sum == num, return True.

The code

def check_perfect_number(num: int) -> bool:
    if num <= 1:
        return False
    total = 1
    i = 2
    while i * i <= num:
        if num % i == 0:
            total += i
            if i != num // i:
                total += num // i
        i += 1
    return total == num

Line-by-line breakdown:

• if num <= 1: 1 has no proper divisors, so it cannot be perfect. Negative numbers and zero are excluded by the problem constraints, but this guard handles them too.
• total = 1: Every number greater than 1 has 1 as a divisor, so start the sum there.
• while i * i <= num: Loop only up to the square root. Using i * i <= num avoids floating-point issues with sqrt.
• if num % i == 0: Check if i divides num evenly.
• total += i: Add the smaller divisor.
• if i != num // i: Avoid double-counting when i equals its pair (this happens when num is a perfect square and i is the exact square root).
• total += num // i: Add the paired divisor.
• return total == num: The definition of a perfect number.

Complexity analysis

You only iterate up to the square root of num, and each iteration does constant work (one modulo and possibly two additions). No extra data structures are needed, so space is constant.

Building blocks

The core technique here is divisor enumeration up to the square root. This pattern appears whenever you need to find all factors of a number efficiently:

i = 2
while i * i <= n:
    if n % i == 0:
        # i is a divisor
        # n // i is also a divisor
    i += 1

You will see this same loop in problems about prime factorization, greatest common divisors, counting divisors, and anywhere you need to decompose a number into its factors. The key realization is always the same: divisors pair up, so you never need to search past the square root.

Edge cases

• num = 1: Only proper divisor would be nothing (no positive integers less than 1 divide it). Sum is 0, which does not equal 1. Return False.
• num = 2: Divisors: just 1. Sum is 1, not 2. Return False.
• Perfect squares like num = 4: Divisors are 1, 2. When i = 2, we get 4 // 2 = 2, which equals i. The guard if i != num // i prevents counting 2 twice. Sum is 3, not 4.
• Large numbers: The algorithm handles inputs up to 10^8 comfortably since it only performs about 10,000 iterations (sqrt of 10^8 is 10,000).

From understanding to recall

The divisor-pair technique is short and elegant, but it is easy to forget the details under time pressure. Did you remember to start the sum at 1? Did you handle the perfect-square edge case? Did you use i * i <= num instead of computing a floating-point square root?

Spaced repetition makes these small decisions automatic. CodeBricks drills the sqrt-divisor loop as a standalone building block. After a few review sessions, you will write the loop without hesitating, whether the problem asks about perfect numbers, prime factorization, or counting factors.

Related posts

• Count Primes - Another math problem that uses efficient divisor/factor reasoning, specifically the Sieve of Eratosthenes
• Happy Number - A math-based problem that combines digit extraction with cycle detection
• Power of Two - A simple math/bit-manipulation check that, like this problem, tests a single numeric property

Commit the pattern to memory

The perfect number problem is a clean example of the "divisors come in pairs" insight. Once you internalize that i and num // i are always a matched set, you will naturally reach for the sqrt loop in any problem that involves factors. Build that reflex with deliberate practice.