Check whether a number is Perfect Number or not

Problem Statement: Perfect Number. Write a program to find whether a number is a perfect number or not.

A perfect number is defined as a number that is the sum of its proper divisors ( all its positive divisors excluding itself). 

Examples:

Example 1:
Input: n=6
Output: 6 is a perfect number

Example 2:
Input: n=15
Output: 15 is not a perfect number

Example 3:
Input: n=28
Output: 28 is a perfect number
Reason:
For 6 and 28 , the sum of their proper divisors (1+2+3) and (1+4+7+14) is equal to the respective numbers and for 15 it is not.

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Basic

Intuition:

We can find the proper divisors of a given number. If their sum is equal to the given number then it is a perfect number.

Approach:

  • We initialise a sum to 0.
  • We can set a loop to iterate from 1 to n-1.
  • In every iteration we check if n is divisible by i, if it is we add it to our sum.
  • After the loop is over, we check whether the given number is equal to our sum, if it is then we the given number is a perfect number, otherwise not.

Code:

C++ Code

#include <iostream>

using namespace std;

bool isPerfect(int n) {

  int sum = 0;
  for (int i = 1; i <= n - 1; i++) {
    if (n % i == 0)
      sum = sum + i;
  }
  if (sum == n)
    return true;
  else return false;
}

int main() {
  // your code goes here
  bool ex1 = isPerfect(6);
  bool ex2 = isPerfect(15);
  bool ex3 = isPerfect(28);

  if (ex1 == true) {
    cout << "6 is a perfect number" << endl;
  } else cout << "6 is not a perfect number" << endl;

  if (ex2 == true) {
    cout << "15 is a perfect number" << endl;
  } else cout << "15 is not a perfect number" << endl;

  if (ex3 == true) {
    cout << "28 is a perfect number" << endl;
  } else cout << "28 is not a perfect number" << endl;

  return 0;
}

Output:

6 is a perfect Number

15 is not a perfect Number

28 is a perfect Number

Time Complexity: O(N)

Reason: We iterate from 1 to n-1.

Space Complexity: O(1)

Reason: We are not using any extra space.

Java Code

import java.io.*;
import java.util.*;

class takeuforward {

  // Driver code

  static boolean isPerfect(int n) {
    int sum = 0;
    for (int i = 1; i <= n - 1; i++) {
      if (n % i == 0)
        sum = sum + i;
    }
    if (sum == n)
      return true;
    else return false;
  }

  public static void main(String[] args) {

    boolean ex1 = isPerfect(6);
    boolean ex2 = isPerfect(15);
    boolean ex3 = isPerfect(28);

    if (ex1 == true) {
      System.out.println("6 is a perfect Number");
    } else System.out.println("6 is a perfect Number");

    if (ex2 == true) {
      System.out.println("15 is a perfect Number");
    } else System.out.println("15 is not a perfect Number");

    if (ex3 == true) {
      System.out.println("28 is a perfect Number");
    } else System.out.println("28 is not a perfect Number");

  }
}

Output:

6 is a perfect Number

15 is not a perfect Number

28 is a perfect Number

Time Complexity: O(N)

Reason: We iterate from 1 to n-1.

Space Complexity: O(1)

Reason: We are not using any extra space.

Solution 2: Efficient Solution

We can use this elegant mathematical property that if n is divisible by k, then n will be also divisible by (n/k).

For example, 28 is divisible by 4, also 28 is divisible by (28/4)=7

In this way, we can reduce our search space from (1 … n-1) to (1… √n ).

Approach:

  • We initialise a sum to 0.
  • We can set a loop to iterate from 1 to √n.
  • In every iteration we check if n is divisible by i, if it is we add it and (n/i) to our sum.
  • After the loop is over, we check whether the given number is equal to our sum, if it is then we the given number is a perfect number, otherwise not.

Note: Please note that if ( i* i ) == n or i==1 r, then we will add only i to the sum as we don’t want to add i two times/ add the number itself to the sum.

Code:

C++ Code

#include <iostream>
using namespace std;


bool isPerfect(int n){
    
    int sum=0;
    for(int i = 1; i*i <= n; i++){
        if(n%i==0)
            if(i*i==n || i==1)
                sum =sum + i;
            else sum = sum+ i + n/i;
    }
    if(sum==n)
        return true;
    else return false;
}

int main() {
	// your code goes here
	bool ex1 = isPerfect(6);
	bool ex2 = isPerfect(15);
	bool ex3 = isPerfect(28);
	
	if(ex1== true){
	    cout<<"6 is a perfect number"<<endl;
	}
	else cout<<"6 is not a perfect number"<<endl;
	
	if(ex2== true){
	    cout<<"15 is a perfect number"<<endl;
	}
	else cout<<"15 is not a perfect number"<<endl;
	
	if(ex3== true){
	    cout<<"28 is a perfect number"<<endl;
	}
	else cout<<"28 is not a perfect number"<<endl;
	
	return 0;
}

Output:

6 is a perfect number
15 is not a perfect number
28 is a perfect number

Time Complexity: O(√N)

Reason: We iterate from 1 to n.

Space Complexity: O(1)

Reason: We are  not using any extra space

Java Code

import java.io.*;
import java.util.*;

class takeuforward {

  // Driver code

  static boolean isPerfect(int n) {
    int sum = 0;
    for (int i = 1; i * i <= n; i++) {
      if (n % i == 0) {
       
        if (i * i == n || i == 1)
          sum = sum + i;
        else sum = sum + i + n / i;

      }
    }
    
    if (sum == n)
      return true;
    else return false;
  }

  public static void main(String[] args) {

    boolean ex1 = isPerfect(6);
    boolean ex2 = isPerfect(15);
    boolean ex3 = isPerfect(28);

    if (ex1 == true) {
      System.out.println("6 is a perfect Number");
    } else System.out.println("6 is a not perfect Number");

    if (ex2 == true) {
      System.out.println("15 is a perfect Number");
    } else System.out.println("15 is not a perfect Number");

    if (ex3 == true) {
      System.out.println("28 is a perfect Number");
    } else System.out.println("28 is not a perfect Number");

  }
}

Output:

6 is a perfect number
15 is not a perfect number
28 is a perfect number

Time Complexity: O(√N)

Reason: We iterate from 1 to n.

Space Complexity: O(1)

Reason: We are  not using any extra space

Special thanks to Anshuman Sharma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article