Perfect Number: flowchart, algorithm and program

This program reads a number n and adds up all its proper divisors, which are the divisors smaller than n itself. If that sum equals n (like 6 or 28), the number is perfect.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Read n.
  3. Step 3: Set sum = 0, i = 1.
  4. Step 4: If i < n, go to step 5; otherwise go to step 8.
  5. Step 5: If n % i == 0, go to step 6; otherwise go to step 7.
  6. Step 6: Set sum = sum + i.
  7. Step 7: Set i = i + 1. Go to step 4.
  8. Step 8: If sum == n && n > 1, go to step 9; otherwise go to step 10.
  9. Step 9: Print n is a perfect number. Go to step 11.
  10. Step 10: Print n is not a perfect number.
  11. Step 11: Stop.

Pseudocode

BEGIN
    READ n
    sum ← 0, i ← 1
    WHILE i < n DO
        IF n % i == 0 THEN
            sum ← sum + i
        END IF
        i ← i + 1
    END WHILE
    IF sum == n && n > 1 THEN
        PRINT n is a perfect number
    ELSE
        PRINT n is not a perfect number
    END IF
END

Program in C, Python and Java

Perfect Number program in C

#include <stdio.h>

int main() {
    int n, i, sum = 0;
    printf("Enter n: ");
    scanf("%d", &n);
    for (i = 1; i < n; i++) {
        if (n % i == 0) {
            sum = sum + i;
        }
    }
    if (sum == n && n > 1) {
        printf("%d is a perfect number\n", n);
    } else {
        printf("%d is not a perfect number\n", n);
    }
    return 0;
}

Perfect Number program in Python

n = int(input("Enter n: "))
sum = 0
for i in range(1, n):
    if n % i == 0:
        sum = sum + i
if sum == n and n > 1:
    print(n, "is a perfect number")
else:
    print(n, "is not a perfect number")

Perfect Number program in Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n: ");
        int n = sc.nextInt();
        int sum = 0;
        for (int i = 1; i < n; i++) {
            if (n % i == 0) {
                sum = sum + i;
            }
        }
        if (sum == n && n > 1) {
            System.out.println(n + " is a perfect number");
        } else {
            System.out.println(n + " is not a perfect number");
        }
    }
}

Sample input: n = 28
Output: 28 is a perfect number

How it works

  • sum starts at 0. It will collect every proper divisor of n.
  • The loop runs i from 1 to n - 1, so n itself is never counted as a divisor.
  • Inside the loop, n % i == 0 means i divides n exactly, so we do sum = sum + i.
  • For n = 28 the divisors found are 1, 2, 4, 7 and 14, and their sum is 28.
  • After the loop, if sum == n and n > 1 we print that n is a perfect number, otherwise we print that it is not.

Dry run (trace table)

StepLineBoxnsumiOutput
13Start
26Read n28
37sum = 0, i = 12801
47i < n?2801
58n % i == 0?2801
69sum = sum + i2811
77i = i + 12812
87i < n?2812
98n % i == 0?2812
109sum = sum + i2832
117i = i + 12833
127i < n?2833
138n % i == 0?2833
147i = i + 12834
157i < n?2834
168n % i == 0?2834
179sum = sum + i2874
187i = i + 12875
197i < n?2875
208n % i == 0?2875

Time and space complexity

Time: O(n) · Space: O(1). The loop runs n-1 times doing constant work each time, using only a few variables.

Common mistakes

  • Looping up to i <= n. This adds n itself to sum, so sum can never equal n for n > 1 and the answer is always wrong.
  • Forgetting to set sum = 0 before the loop, which gives a garbage starting value.
  • Skipping the n > 1 check. For n = 1 the loop never runs, so sum is 0 and the program is correct, but for n = 0 or negative input the result is meaningless.

Viva questions

Q1. What is a perfect number? Give two examples.

A perfect number equals the sum of its proper divisors, meaning all divisors except the number itself. 6 (1+2+3) and 28 (1+2+4+7+14) are examples.

Q2. Why is sum initialised to 0 and not 1?

sum is an accumulator for addition, so it must start at 0 so it doesn't change the total. Starting at 1 would add an extra 1 to every result and give wrong answers.

Q3. What does the condition n % i == 0 check?

It checks whether i divides n exactly with no remainder. If so, i is a divisor of n and gets added to sum.

Q4. Why does the loop run only up to i < n and not i <= n?

We want proper divisors, which exclude n itself. If n were included, the sum would always be at least n + 1 for n > 1, and no number would ever be perfect.

Q5. What happens if the user enters 1, 0 or a negative number?

For these the loop never runs, so sum stays 0. For 1, sum (0) is not equal to 1 anyway. For 0, sum equals n, which is why the n > 1 check is needed so 0 is not wrongly called perfect. Negative numbers give sum 0, which is not equal to n, so they are reported as not perfect.

Q6. Why is n > 1 included in the condition on line 12?

Without it, n = 0 would give sum == n (0 == 0) and be reported as perfect, which is wrong. Perfect numbers are positive integers, with 6 the smallest.

Q7. What is the time complexity of this program, and can it be improved?

It is O(n) because the loop runs n-1 times. It can be improved to O(sqrt(n)) by looping only up to sqrt(n) and adding both i and n/i whenever i divides n, taking care not to count a repeated square root twice and not to include n itself.

Q8. What would change if you wanted to print the divisors too, or check for an abundant number instead?

To print the divisors, add a printf of i inside the if block on line 9. For an abundant number, the logic is the same but the final condition becomes sum > n instead of sum == n.

Frequently asked questions

What is a perfect number?

A perfect number is a positive integer that equals the sum of its proper divisors (divisors excluding itself). 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14 are examples.

Why does the loop stop at n - 1?

Proper divisors do not include n itself. Stopping at i < n keeps n out of the sum, so we can compare sum directly with n.

How can I make the perfect number check faster?

You only need to loop up to n / 2, since no proper divisor is larger than n / 2. A further trick is to loop up to the square root of n and add both i and n / i, which is much faster for large n.

More programs

← All programs

Try AI Flowchart free →