← Back to Overview

Perfect Number Check

Concept Explanation

What is it?

A perfect number is a positive integer that is equal to the sum of its proper positive divisors (divisors excluding the number itself). For example, 6 is a perfect number because its proper divisors are 1, 2, and 3, and 1 + 2 + 3 = 6. The next perfect number is 28 (1+2+4+7+14 = 28).

Why is it important?

Perfect numbers are a fascinating topic in number theory and have been studied since ancient times. While not directly applied in everyday programming as frequently as prime numbers, the algorithm to find them is an excellent exercise in loop optimization, conditional logic, and mathematical reasoning.

Where is it used?

• Number Theory Research: Continued study of properties of integers.
• Algorithm Practice: Used in coding challenges and interviews to test a programmer's ability to implement mathematical concepts efficiently.

Real-world example

There isn't a direct "real-world" application like cryptography for perfect numbers. Their importance lies more in theoretical mathematics and as a historical curiosity that has driven mathematical exploration. It's a classic problem for teaching iterative algorithms and optimization.

---

Algorithm

1. Start.
2. Get a positive integer num from the user.
3. If num is less than or equal to 1, it cannot be a perfect number.
4. Initialize a variable sum_of_divisors to 1 (since 1 is always a proper divisor).
5. Iterate from i = 2 up to the square root of num. a. If num is divisible by i: i. Add i to sum_of_divisors. ii. If i * i is not equal to num (meaning i and num/i are distinct divisors), add num / i to sum_of_divisors.
6. If sum_of_divisors is equal to num, then num is a perfect number.
7. Display the result.
8. End.

Optimization Note: We only need to check for divisors only up to the square root of num significantly improves efficiency. If i is a divisor, then num/i is also a divisor.

Edge Cases: - Inputting non-integer values (handled by language-specific error mechanisms or explicit validation). - num = 0 or num = 1: These are not considered perfect numbers. - Negative numbers: Perfect numbers are defined as positive integers.

---

Implementations

Java (JDK 17)Python (3.10+)C (C99)Oracle (19c)

import java.util.Scanner;

public class PerfectNumber {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter a number: ");
        int num = scanner.nextInt();

        int sumOfDivisors = 1; // 1 is always a divisor for any number > 1

        if (num <= 1) {
            System.out.println(num + " is NOT a perfect number (must be a positive integer > 1).");
        } else {
            // Find proper divisors and sum them
            // We check divisors up to sqrt(num)
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    sumOfDivisors += i;
                    if (i * i != num) { // Avoid adding the same divisor twice for perfect squares
                        sumOfDivisors += num / i;
                    }
                }
            }

            if (sumOfDivisors == num) {
                System.out.println(num + " is a PERFECT number.");
            } else {
                System.out.println(num + " is NOT a perfect number.");
            }
        }

        scanner.close();
    }
}

import math

# Get a number from the user
num_str = input("Enter a number: ")
num = int(num_str)

print(f"Input Number: {num}")

sum_of_divisors = 1 # 1 is always a divisor for any number > 1

if num <= 1:
    print(f"{num} is NOT a perfect number (must be a positive integer > 1).")
else:
    # Find proper divisors and sum them
    # We check divisors up to sqrt(num)
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            sum_of_divisors += i
            if i * i != num: # Avoid adding the same divisor twice for perfect squares
                sum_of_divisors += num // i

    if sum_of_divisors == num:
        print(f"{num} is a PERFECT number.")
    else:
        print(f"{num} is NOT a perfect number.")

#include <stdio.h>
#include <math.h> // For sqrt()

int main() {
    int num, i;
    int sum_of_divisors = 1; // 1 is always a divisor for any number > 1

    printf("Enter a positive integer: ");
    scanf("%d", &num);

    printf("Input Number: %d\n", num);

    if (num <= 1) {
        printf("%d is NOT a perfect number (must be a positive integer > 1).\n", num);
        return 0; // Exit program
    }

    // Find proper divisors and sum them
    // We check divisors up to sqrt(num)
    for (i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            sum_of_divisors += i;
            if (i * i != num) { // Avoid adding the same divisor twice for perfect squares
                sum_of_divisors += num / i;
            }
        }
    }

    if (sum_of_divisors == num) {
        printf("%d is a PERFECT number.\n", num);
    } else {
        printf("%d is NOT a perfect number.\n", num);
    }

    return 0;
}

SET SERVEROUTPUT ON;
DECLARE
  input_num     NUMBER := &Enter_an_Integer;
  sum_of_divisors NUMBER := 0;
BEGIN
  DBMS_OUTPUT.PUT_LINE('Input Number: ' || input_num);

  IF input_num <= 0 THEN
    DBMS_OUTPUT.PUT_LINE(input_num || ' is not a perfect number (must be a positive integer).');
  ELSE
    sum_of_divisors := 1; -- 1 is always a proper divisor for positive integers
    FOR i IN 2 .. TRUNC(SQRT(input_num)) LOOP -- Iterate up to the square root
      IF MOD(input_num, i) = 0 THEN
        sum_of_divisors := sum_of_divisors + i;
        IF i * i != input_num THEN -- If i and input_num/i are distinct
          sum_of_divisors := sum_of_divisors + (input_num / i);
        END IF;
      END IF;
    END LOOP;

    IF sum_of_divisors = input_num THEN
      DBMS_OUTPUT.PUT_LINE(input_num || ' is a PERFECT number.');
    ELSE
      DBMS_OUTPUT.PUT_LINE(input_num || ' is NOT a perfect number.');
    END IF;
  END IF;
END;
/

Explanation

• Java: Uses a for loop to find divisors up to the square root, optimizing the check. Math.sqrt() and the modulo operator % are key.
• Python: Similar logic to Java, utilizing math.sqrt() and range() for iteration. Handles integer conversion from input.
• C: Employs a for loop up to sqrt(num). Includes math.h for sqrt(). Handles cases where num/i is also a divisor and distinct from i.
• Oracle: Implemented in PL/SQL. Uses TRUNC(SQRT()) for the loop limit and MOD() for divisibility checks. Handles num <= 0 explicitly.

Complexity Analysis

• Time Complexity: O(sqrt(n)) - The loop runs approximately up to the square root of the input number.
• Space Complexity: O(1) - A fixed number of variables are used.

Flowchart

graph TD
    A[Start] --> B[Get Integer num]
    B --> C{num <= 1?}
    C -- Yes --> D[Display Not a Perfect Number]
    C -- No --> E[sum_of_divisors = 1]
    E --> F[i = 2]
    F --> G{i*i <= num?}
    G -- Yes --> H{num % i == 0?}
    G -- No --> L{sum_of_divisors == num?}
    G -- Yes --> H[sum_of_divisors += i]
    H --> I{i*i != num?}
    I -- Yes --> J[sum_of_divisors += num / i]
    J --> K[i++]
    I -- No --> K
    G -- No --> K
    K --> F
    F --> L{sum_of_divisors == num?}
    L -- Yes --> M[Display PERFECT Number]
    L -- No --> N[Display NOT a Perfect Number]
    M --> O[End]
    N --> O
    D --> O

Sample Dry Run

Step	num	i	sum_of_divisors	num % i	i*i != num	num / i	Description
Input	6	-	-	-	-	-	User enters 6
num <= 1?	6	-	-	-	-	-	False
Init	6	-	1	-	-	-	sum_of_divisors = 1
Loop i=2	6	2	1	0	-	-	6 % 2 == 0 (True)
	6	2	1+2=3	-	-	-	sum_of_divisors += 2
i*i != num?	6	2	3	-	True (4!=6)	3	num/i = 3
	6	2	3+3=6	-	-	-	sum_of_divisors += 3
Loop End	-	-	-	-	-	-	Loop finishes (sqrt(6) is approx 2.44)
sum_of_divisors == num?	6	-	6	-	-	-	True (6 == 6)
Output	-	-	-	-	-	-	Display "6 is a PERFECT number."
End	-	-	-	-	-	-	Program terminates

Practice Problems

Easy

• Modify the program to find all perfect numbers up to a given limit (e.g., 1000).
• Write a program to find if a number is an "abundant" or "deficient" number.

Medium

• Implement a function that takes a number and returns a list of its proper divisors.
• Optimize the perfect number check for larger numbers by pre-calculating primes.

Hard

• Explore the relationship between perfect numbers and Mersenne primes.
• Implement a program to find "amicable numbers" (a pair of numbers where the sum of proper divisors of each equals the other number).

---

"Programming is the art of telling another human being what one wants the computer to do." - Donald Knuth