AlgoInsight

DSA problem

Perfect Number

EasyRecursionPattern: MathbeginnerFree

Given an integer N, determine whether it is a perfect number. A perfect number is a positive integer equal to the sum of its proper divisors (all positive divisors excluding the number itself).

The first few perfect numbers are 6 (1 + 2 + 3), 28 (1 + 2 + 4 + 7 + 14), and 496. To check, sum all divisors of N except N itself and test whether the total equals N.

The naive approach scans every number from 1 to N-1 in O(N). The optimized approach scans only up to sqrt(N): for each divisor i, both i and N / i are divisors, so add both - being careful not to double-count when i == N / i (a perfect square) and not to add N itself. This brings the cost down to O(sqrt(N)). Perfect numbers are rare (only 51 are known) and are deeply connected to Mersenne primes; this problem reinforces the sqrt(N) optimization for divisor problems.

Examples

Example 1
Input: N = 28
Output: true
Explanation: The proper divisors of 28 are 1, 2, 4, 7, 14 and 1 + 2 + 4 + 7 + 14 = 28, so 28 is a perfect number.
Example 2
Input: N = 12
Output: false
Explanation: The proper divisors of 12 are 1, 2, 3, 4, 6 and their sum is 16, which is not equal to 12.
Example 3
Input: N = 6
Output: true
Explanation: 1 + 2 + 3 = 6, the smallest perfect number.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

mathnumber-theory

Browse all DSA problems