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
- Step 1: Start.
- Step 2: Read n.
- Step 3: Set sum = 0, i = 1.
- Step 4: If i < n, go to step 5; otherwise go to step 8.
- Step 5: If n % i == 0, go to step 6; otherwise go to step 7.
- Step 6: Set sum = sum + i.
- Step 7: Set i = i + 1. Go to step 4.
- Step 8: If sum == n && n > 1, go to step 9; otherwise go to step 10.
- Step 9: Print n is a perfect number. Go to step 11.
- Step 10: Print n is not a perfect number.
- 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)
| Step | Line | Box | n | sum | i | Output |
|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||
| 2 | 6 | Read n | 28 | |||
| 3 | 7 | sum = 0, i = 1 | 28 | 0 | 1 | |
| 4 | 7 | i < n? | 28 | 0 | 1 | |
| 5 | 8 | n % i == 0? | 28 | 0 | 1 | |
| 6 | 9 | sum = sum + i | 28 | 1 | 1 | |
| 7 | 7 | i = i + 1 | 28 | 1 | 2 | |
| 8 | 7 | i < n? | 28 | 1 | 2 | |
| 9 | 8 | n % i == 0? | 28 | 1 | 2 | |
| 10 | 9 | sum = sum + i | 28 | 3 | 2 | |
| 11 | 7 | i = i + 1 | 28 | 3 | 3 | |
| 12 | 7 | i < n? | 28 | 3 | 3 | |
| 13 | 8 | n % i == 0? | 28 | 3 | 3 | |
| 14 | 7 | i = i + 1 | 28 | 3 | 4 | |
| 15 | 7 | i < n? | 28 | 3 | 4 | |
| 16 | 8 | n % i == 0? | 28 | 3 | 4 | |
| 17 | 9 | sum = sum + i | 28 | 7 | 4 | |
| 18 | 7 | i = i + 1 | 28 | 7 | 5 | |
| 19 | 7 | i < n? | 28 | 7 | 5 | |
| 20 | 8 | n % i == 0? | 28 | 7 | 5 |
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.