Check Whether a Given Number Is a Perfect Number

A number is perfect when the sum of its proper divisors equals the number itself. Six is the smallest: its proper divisors are 1, 2, and 3, and 1 + 2 + 3 = 6.

This check appears in placement tests at service-tier companies that include basic number-theory questions in their online rounds. The problem has two solutions worth knowing: a brute-force O(N) loop and an optimised O(√N) version. Both are short to write; only one is worth submitting under time pressure.

What Is a Perfect Number?

A perfect number is a positive integer N where the sum of its proper divisors (every positive divisor of N except N itself) equals N exactly.

Verified examples (each re-derived from first principles):

• 6: proper divisors = 3 → 1 + 2 + 3 = 6 ✓
• 28: proper divisors = 14 → 1 + 2 + 4 + 7 + 14 = 28 ✓
• 496: proper divisors = 248 → sum = 496 ✓
• 8128: 8128 = 2^6 × 127; proper divisors sum to 8128 ✓

These are the only four perfect numbers below 33,550,336, per the OEIS record for sequence A000396. The next perfect number after 8128 is 33,550,336.

Two quick non-examples:

• 12: proper divisors = 6 → sum = 16. More than 12, so 12 is abundant, not perfect.
• 8: proper divisors = 4 → sum = 7. Less than 8, so 8 is deficient.

Note on edge cases: 1 is not perfect (no proper divisors; sum is 0). Most implementations start from N = 2.

Two Methods to Check for Perfection

Method 1: Brute Force, O(N)

Walk through every integer from 1 to N-1. Any integer i in that range where N % i == 0 is a proper divisor. Accumulate the sum and compare to N at the end.

Step-by-step for N = 28:

• i = 1: 28 % 1 == 0, add 1 (sum = 1)
• i = 2: 28 % 2 == 0, add 2 (sum = 3)
• i = 3: 28 % 3 ≠ 0, skip
• i = 4: 28 % 4 == 0, add 4 (sum = 7)
• i = 5, 6: no divisors
• i = 7: 28 % 7 == 0, add 7 (sum = 14)
• i = 8 to 13: no divisors
• i = 14: 28 % 14 == 0, add 14 (sum = 28)
• i = 15 to 27: no divisors
• Final sum = 28 = N, so 28 is perfect.

This runs in O(N) time. For small numbers it works fine; for very large N it becomes slow.

Method 2: Optimised, O(√N)

Divisors come in pairs. If i divides N, then N/i also divides N. Iterating from 1 to √N and collecting both i and N/i in each step finds all divisors in far fewer iterations.

Two rules for correct pairing:

1. Never add N itself to the sum (when i = 1, N/i = N; skip the N/i part for that case).
2. When i == N/i (N is a perfect square and i is its square root), add i only once.

Step-by-step for N = 28 (√28 ≈ 5.29, so loop i = 1 to 5):

• i = 1: 28 % 1 == 0. Add 1. N/i = 28 (that is N itself; skip). Sum = 1.
• i = 2: 28 % 2 == 0. Add 2. Add N/i = 14. Sum = 17.
• i = 3: 28 % 3 ≠ 0, skip.
• i = 4: 28 % 4 == 0. Add 4. Add N/i = 7. Sum = 28.
• i = 5: 28 % 5 ≠ 0, skip.
• Final sum = 28 = N, perfect. Five iterations instead of 27.

The technique of pairing divisors around √N is the same idea that makes counting divisors in a range efficient. If you want a fuller treatment of how that loop structure compares across problems, the GeeksforGeeks writeup on perfect numbers covers the same pattern from a slightly different angle.

C Program to Check Perfect Number

Method 1: O(N)

#include <stdio.h>

int isPerfect(int n) {
    if (n <= 1) return 0;
    int sum = 0;
    for (int i = 1; i < n; i++) {
        if (n % i == 0)
            sum += i;
    }
    return sum == n;
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    if (isPerfect(num))
        printf("%d is a perfect number.\n", num);
    else
        printf("%d is not a perfect number.\n", num);
    return 0;
}

Method 2: O(√N)

#include <stdio.h>
#include <math.h>

int isPerfectOptimised(int n) {
    if (n <= 1) return 0;
    int sum = 1;   /* 1 is always a proper divisor for n > 1 */
    int sqrtN = (int)sqrt((double)n);
    for (int i = 2; i <= sqrtN; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i)
                sum += n / i;
        }
    }
    return sum == n;
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    if (isPerfectOptimised(num))
        printf("%d is a perfect number.\n", num);
    else
        printf("%d is not a perfect number.\n", num);
    return 0;
}

Key lines to understand:

• sum = 1 initialises with 1 because 1 divides every integer greater than 1.
• The loop runs from i = 2 to sqrtN (inclusive). The <= bound ensures perfect squares are handled.
• if (i != n / i) prevents double-counting when i is the exact square root of n.
• Compile with gcc program.c -lm -o program to link the math library for sqrt().

Python Program to Check Perfect Number

Python’s range() and sum() make the brute-force version a one-liner. The O(N) cost still applies, so write the optimised version for interviews.

Method 1: O(N)

def is_perfect(n):
    if n <= 1:
        return False
    return sum(i for i in range(1, n) if n % i == 0) == n

num = int(input("Enter a number: "))
if is_perfect(num):
    print(f"{num} is a perfect number.")
else:
    print(f"{num} is not a perfect number.")

Method 2: O(√N)

import math

def is_perfect_optimised(n):
    if n <= 1:
        return False
    divisor_sum = 1
    sqrt_n = int(math.isqrt(n))
    for i in range(2, sqrt_n + 1):
        if n % i == 0:
            divisor_sum += i
            if i != n // i:
                divisor_sum += n // i
    return divisor_sum == n

num = int(input("Enter a number: "))
result = "a perfect number" if is_perfect_optimised(num) else "not a perfect number"
print(f"{num} is {result}.")

math.isqrt(n) (Python 3.8+) returns the integer square root without floating-point rounding issues, which makes it safer than int(math.sqrt(n)) for large inputs.

Java Program to Check Perfect Number

import java.util.Scanner;

public class PerfectNumber {

    // Method 1: O(N)
    static boolean isPerfect(int n) {
        if (n <= 1) return false;
        int sum = 0;
        for (int i = 1; i < n; i++) {
            if (n % i == 0) sum += i;
        }
        return sum == n;
    }

    // Method 2: O(sqrt(N))
    static boolean isPerfectOptimised(int n) {
        if (n <= 1) return false;
        int sum = 1;
        int sqrtN = (int) Math.sqrt(n);
        for (int i = 2; i <= sqrtN; i++) {
            if (n % i == 0) {
                sum += i;
                if (i != n / i) sum += n / i;
            }
        }
        return sum == n;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int num = sc.nextInt();
        System.out.println(num + (isPerfectOptimised(num)
            ? " is a perfect number."
            : " is not a perfect number."));
    }
}

The Java version mirrors the C logic closely. Math.sqrt() returns a double, so casting to int gives the floor, which is correct for this use case.

Time Complexity and Space Complexity

Method	Time Complexity	Space Complexity	Notes
Brute force	O(N)	O(1)	Loops 1 to N-1; slow for large N
Optimised	O(√N)	O(1)	Loops 1 to √N; preferred for interviews

Both methods use only a single accumulator variable, so space complexity is O(1) in both cases. For a broader breakdown of how loop bounds affect algorithm costs, see the guide on space complexity of algorithms with examples.

The sum-of-digits program and the Armstrong number check follow the same digit-and-divisor accumulation pattern, making them useful companion exercises before attempting perfect-number variants.

From Divisor Loops to Real-World Code

The O(√N) optimisation here is a clean instance of recognising symmetry in a problem: instead of O(N) brute-force, you cut the work to O(√N) by pairing each divisor with its complement. That same instinct turns up constantly in production code, from hash-table design to tokenisation pipelines.

If you’re preparing for coding rounds at service-tier companies and want to move beyond textbook exercises, TinkerLLM at ₹299 lets you build small LLM-backed tools in Python. The loop-and-accumulate pattern you just wrote for divisors is directly analogous to how token frequency tables are built under the hood.