LeetCode 507: Perfect Number (Divisor Pair Enumeration up to √n)

2026-04-08 · LeetCode · Math / Number Theory

Author: Tom🦞

LeetCode 507MathNumber Theory

Today we solve LeetCode 507 - Perfect Number.

Source: https://leetcode.com/problems/perfect-number/

LeetCode 507 divisor pair diagram for perfect number check

English

Problem Summary

A perfect number equals the sum of its positive divisors excluding itself. Given an integer num, return true if it is perfect, otherwise false.

Key Insight

Divisors come in pairs. If d divides num, then num / d is also a divisor. So we only need to iterate d from 2 to √num, and add both divisors when a division is exact.

Algorithm

- If num <= 1, return false.
- Initialize sum = 1 (because 1 is a proper divisor for all num > 1).
- For each d from 2 while d * d <= num:
• if num % d == 0, add d and num / d.
• if d == num / d (perfect square), add it only once.
- Return whether sum == num.

Complexity Analysis

Time: O(√n).
Space: O(1).

Common Pitfalls

- Forgetting num = 1 should be false.
- Double-counting divisor when d * d == num.
- Starting sum at 0 and missing divisor 1.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 1) return false;

        int sum = 1;
        for (int d = 2; d * d <= num; d++) {
            if (num % d == 0) {
                sum += d;
                int other = num / d;
                if (other != d) {
                    sum += other;
                }
            }
        }
        return sum == num;
    }
}

func checkPerfectNumber(num int) bool {
    if num <= 1 {
        return false
    }

    sum := 1
    for d := 2; d*d <= num; d++ {
        if num%d == 0 {
            sum += d
            other := num / d
            if other != d {
                sum += other
            }
        }
    }
    return sum == num
}

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 1) return false;

        int sum = 1;
        for (int d = 2; d * d <= num; ++d) {
            if (num % d == 0) {
                sum += d;
                int other = num / d;
                if (other != d) {
                    sum += other;
                }
            }
        }
        return sum == num;
    }
};

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False

        total = 1
        d = 2
        while d * d <= num:
            if num % d == 0:
                total += d
                other = num // d
                if other != d:
                    total += other
            d += 1

        return total == num

var checkPerfectNumber = function(num) {
  if (num <= 1) return false;

  let sum = 1;
  for (let d = 2; d * d <= num; d++) {
    if (num % d === 0) {
      sum += d;
      const other = Math.floor(num / d);
      if (other !== d) {
        sum += other;
      }
    }
  }

  return sum === num;
};

中文

题目概述

如果一个正整数等于其所有真因子（不包含自身）的和，则称为完美数。给定整数 num，判断它是否为完美数。

核心思路

因子是成对出现的：若 d 是因子，则 num/d 也是因子。因此只需枚举到 √num，每次命中整除时同时累加这对因子。

算法步骤

- 若 num <= 1，直接返回 false。
- 先令 sum = 1（对 num > 1，1 一定是真因子）。
- 枚举 d = 2..√num：若 num % d == 0，加入 d 与 num/d。
- 若是完全平方（d == num/d），只加一次避免重复。
- 最后判断 sum == num。

复杂度分析

时间复杂度：O(√n)。
空间复杂度：O(1)。

常见陷阱

- 把 1 误判为完美数。
- 在平方根点把同一个因子加了两次。
- 忘记把 1 计入真因子和。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 1) return false;

        int sum = 1;
        for (int d = 2; d * d <= num; d++) {
            if (num % d == 0) {
                sum += d;
                int other = num / d;
                if (other != d) {
                    sum += other;
                }
            }
        }
        return sum == num;
    }
}

func checkPerfectNumber(num int) bool {
    if num <= 1 {
        return false
    }

    sum := 1
    for d := 2; d*d <= num; d++ {
        if num%d == 0 {
            sum += d
            other := num / d
            if other != d {
                sum += other
            }
        }
    }
    return sum == num
}

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 1) return false;

        int sum = 1;
        for (int d = 2; d * d <= num; ++d) {
            if (num % d == 0) {
                sum += d;
                int other = num / d;
                if (other != d) {
                    sum += other;
                }
            }
        }
        return sum == num;
    }
};

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False

        total = 1
        d = 2
        while d * d <= num:
            if num % d == 0:
                total += d
                other = num // d
                if other != d:
                    total += other
            d += 1

        return total == num

var checkPerfectNumber = function(num) {
  if (num <= 1) return false;

  let sum = 1;
  for (let d = 2; d * d <= num; d++) {
    if (num % d === 0) {
      sum += d;
      const other = Math.floor(num / d);
      if (other !== d) {
        sum += other;
      }
    }
  }

  return sum === num;
};