Semiperfect Number

Namachila November 19, 2025

0 0 12 minutes read

In number theory, a semiperfect number or pseudoperfect number is a natural number n that is equal to the sum of all or some of its proper divisors. A semiperfect number that is equal to the sum of all its proper divisors is a perfect number.
Given a number, the task is to check if the number is a semi-perfect number or not.

Examples:

Input: 40
Output: The number is Semiperfect
1+4+5+10+20=40

Input: 70
Output: The number is not Semiperfect
The first few semiperfect numbers are
6, 12, 18, 20, 24, 28, 30, 36, 40

Approach: Store all the factors of the number in a data-structure(Vector or Arrays). Sort them in increasing order. Once the factors are stored, Dynamic programming can be used to check if any combination forms N or not. The problem becomes similar to the Subset Sum Problem. We can use the same approach and check if the number is a semi-perfect number or not.

Below is the implementation of the above approach.

C++

// C++ program to check if the number
// is semi-perfect or not
#include <bits/stdc++.h>
using namespace std;
 
// code to find all the factors of
// the number excluding the number itself
vector<int> factors(int n)
{
    // vector to store the factors
    vector<int> v;
    v.push_back(1);
 
    // note that this loop runs till sqrt(n)
    for (int i = 2; i <= sqrt(n); i++) {
 
        // if the value of i is a factor
        if (n % i == 0) {
            v.push_back(i);
 
            // condition to check the
            // divisor is not the number itself
            if (n / i != i) {
                v.push_back(n / i);
            }
        }
    }
    // return the vector
    return v;
}
 
// Function to check if the
// number is semi-perfect or not
bool check(int n)
{
    vector<int> v;
 
    // find the divisors
    v = factors(n);
 
    // sorting the vector
    sort(v.begin(), v.end());
 
    int r = v.size();
 
    // subset to check if no is semiperfect
    bool subset[r + 1][n + 1];
 
    // initialising 1st column to true
    for (int i = 0; i <= r; i++)
        subset[i][0] = true;
 
    // initializing 1st row except zero position to 0
    for (int i = 1; i <= n; i++)
        subset[0][i] = false;
 
    // loop to find whether the number is semiperfect
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= n; j++) {
 
            // calculation to check if the
            // number can be made by summation of divisors
            if (j < v[i - 1])
                subset[i][j] = subset[i - 1][j];
            else {
                subset[i][j] = subset[i - 1][j] || 
                               subset[i - 1][j - v[i - 1]];
            }
        }
    }
 
    // if not possible to make the
    // number by any combination of divisors
    if ((subset[r][n]) == 0)
        return false;
    else
        return true;
}
 
// driver code to check if possible
int main()
{
    int n = 40;
    if (check(n))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Java

// Java program to check 
// if the number is 
// semi-perfect or not
import java.util.*;
class GFG{
 
// Code to find all the factors of
// the number excluding the number itself
static Vector<Integer> factors(int n)
{
  // vector to store the factors
  Vector<Integer> v = new Vector<>();
  v.add(1);
 
  // note that this loop runs till Math.sqrt(n)
  for (int i = 2; i <= Math.sqrt(n); i++) 
  {
    // if the value of i is a factor
    if (n % i == 0) 
    {
      v.add(i);
 
      // condition to check the
      // divisor is not the number itself
      if (n / i != i) 
      {
        v.add(n / i);
      }
    }
  }
   
  // return the vector
  return v;
}
 
// Function to check if the
// number is semi-perfect or not
static boolean check(int n)
{
  Vector<Integer> v = new Vector<>();
 
  // find the divisors
  v = factors(n);
 
  // sorting the vector
  Collections.sort(v);
 
  int r = v.size();
 
  // subset to check if no 
  // is semiperfect
  boolean [][]subset = 
          new boolean[r + 1][n + 1];
 
  // initialising 1st column to true
  for (int i = 0; i <= r; i++)
    subset[i][0] = true;
 
  // initializing 1st row except 
  // zero position to 0
  for (int i = 1; i <= n; i++)
    subset[0][i] = false;
 
  // loop to find whether the 
  // number is semiperfect
  for (int i = 1; i <= r; i++) 
  {
    for (int j = 1; j <= n; j++) 
    {
      // calculation to check if the
      // number can be made by 
      // summation of divisors
      if (j < v.elementAt(i - 1))
        subset[i][j] = subset[i - 1][j];
      else
      {
        subset[i][j] = subset[i - 1][j] || 
                       subset[i - 1][j - v.elementAt(i - 1)];
      }
    }
  }
 
  // If not possible to make the
  // number by any combination of divisors
  if ((subset[r][n]) == false)
    return false;
  else
    return true;
}
 
// Driver code to check if possible
public static void main(String[] args)
{
  int n = 40;
  if (check(n))
    System.out.print("Yes");
  else
    System.out.print("No");
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program to check if the number
# is semi-perfect or not
import math
 
# code to find all the factors of
# the number excluding the number itself
def factors( n):
 
    # vector to store the factors
    v = []
    v.append(1)
 
    # note that this loop runs till sqrt(n)
    sqt = int(math.sqrt(n))
    for i in range(2, sqt + 1):
 
        # if the value of i is a factor
        if (n % i == 0):
            v.append(i)
 
            # condition to check the
            # divisor is not the number itself
            if (n // i != i):
                v.append(n // i)
                 
    # return the vector
    return v
 
# Function to check if the
# number is semi-perfect or not
def check( n):
 
    v = []
 
    # find the divisors
    v = factors(n)
 
    # sorting the vector
    v.sort()
 
    r = len(v)
 
    # subset to check if no is semiperfect
    subset = [[ 0 for i in range(n + 1)]
                  for j in range(r + 1)]
 
    # initialising 1st column to true
    for i in range(r + 1):
        subset[i][0] = True
 
    # initializing 1st row except zero position to 0
    for i in range(1, n + 1):
        subset[0][i] = False
 
    # loop to find whether the number is semiperfect
    for i in range(1, r + 1):
        for j in range(1, n + 1):
 
            # calculation to check if the
            # number can be made by summation of divisors
            if (j < v[i - 1]):
                subset[i][j] = subset[i - 1][j];
            else:
                subset[i][j] = (subset[i - 1][j] or
                                subset[i - 1][j - v[i - 1]])
 
    # if not possible to make the
    # number by any combination of divisors
    if ((subset[r][n]) == 0):
        return False
    else:
        return True
 
# Driver Code
if __name__ == "__main__":
    n = 40
    if (check(n)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by ChitraNayal

C#

// C# program to check 
// if the number is 
// semi-perfect or not
using System;
using System.Collections.Generic;
class GFG{
 
// Code to find all the 
// factors of the number 
// excluding the number itself
static List<int> factors(int n)
{
  // vector to store the factors
  List<int> v = new List<int>();
  v.Add(1);
 
  // note that this loop runs 
  // till Math.Sqrt(n)
  for (int i = 2; 
           i <= Math.Sqrt(n); i++) 
  {
    // if the value of i is 
    // a factor
    if (n % i == 0) 
    {
      v.Add(i);
 
      // condition to check the
      // divisor is not the number 
      // itself
      if (n / i != i) 
      {
        v.Add(n / i);
      }
    }
  }
 
// return the vector
return v;
}
 
// Function to check if the
// number is semi-perfect or not
static bool check(int n)
{
  List<int> v = new List<int>();
 
  // find the divisors
  v = factors(n);
 
  // sorting the vector
  v.Sort();
 
  int r = v.Count;
 
  // subset to check if no 
  // is semiperfect
  bool [,]subset = new bool[r + 1,
                            n + 1];
 
  // initialising 1st column 
  // to true
  for (int i = 0; i <= r; i++)
    subset[i, 0] = true;
 
  // initializing 1st row except 
  // zero position to 0
  for (int i = 1; i <= n; i++)
    subset[0, i] = false;
 
  // loop to find whether the 
  // number is semiperfect
  for (int i = 1; i <= r; i++) 
  {
    for (int j = 1; j <= n; j++) 
    {
      // calculation to check if the
      // number can be made by 
      // summation of divisors
      if (j < v[i - 1])
        subset[i, j] = subset[i - 1, j];
      else
      {
        subset[i, j] = subset[i - 1, j] || 
        subset[i - 1, (j - v[i - 1])];
      }
    }
  }
 
  // If not possible to make 
  // the number by any combination 
  // of divisors
  if ((subset[r, n]) == false)
    return false;
  else
    return true;
}
 
// Driver code 
public static void Main(String[] args)
{
  int n = 40;
   
  if (check(n))
    Console.Write("Yes");
  else
    Console.Write("No");
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
// Javascript program to check
// if the number is
// semi-perfect or not
 
// Code to find all the factors of
// the number excluding the number itself
function factors(n)
{
    // vector to store the factors
  let v = [];
  v.push(1);
  
  // note that this loop runs till Math.sqrt(n)
  for (let i = 2; i <= Math.sqrt(n); i++)
  {
    // if the value of i is a factor
    if (n % i == 0)
    {
      v.push(i);
  
      // condition to check the
      // divisor is not the number itself
      if (Math.floor(n / i) != i)
      {
        v.push(Math.floor(n / i));
      }
    }
  }
    
  // return the vector
  return v;
}
 
// Function to check if the
// number is semi-perfect or not
function check(n)
{
    let v = [] ;
  
  // find the divisors
  v = factors(n);
  
  // sorting the vector
  v.sort(function(a,b){return a-b;});
  
  let r = v.length;
  
  // subset to check if no
  // is semiperfect
  let subset = new Array(r + 1);
  for(let i=0;i<r+1;i++)
  {
      subset[i]=new Array(n+1);
    for(let j=0;j<n+1;j++)
    {
        subset[i][j]=false;
    }
  }
  
  // initialising 1st column to true
  for (let i = 0; i <= r; i++)
    subset[i][0] = true;
  
  // initializing 1st row except
  // zero position to 0
  for (let i = 1; i <= n; i++)
    subset[0][i] = false;
  
  // loop to find whether the
  // number is semiperfect
  for (let i = 1; i <= r; i++)
  {
    for (let j = 1; j <= n; j++)
    {
      // calculation to check if the
      // number can be made by
      // summation of divisors
      if (j < v[i-1])
        subset[i][j] = subset[i - 1][j];
      else
      {
        subset[i][j] = subset[i - 1][j] ||
                       subset[i - 1][j - v[i-1]];
      }
    }
  }
  
  // If not possible to make the
  // number by any combination of divisors
  if ((subset[r][n]) == false)
    return false;
  else
    return true;
}
 
// Driver code to check if possible
let n = 40;
if (check(n))
    document.write("Yes");
else
    document.write("No");
 
     
     
// This code is contributed by rag2127
</script>

Output

Yes

Time Complexity: O(number of factors * N)
Auxiliary Space: O(number of factors * N)

Efficient approach : Space optimization

In previous approach the current value subset[i][j] is only depend upon the current and previous row values of subset matrix. So to optimize the space complexity we use a single 1D array to store the computations.

Implementation:

C++

// C++ program to check if the number
// is semi-perfect or not
#include <bits/stdc++.h>
using namespace std;
 
// code to find all the factors of
// the number excluding the number itself
vector<int> factors(int n)
{
    // vector to store the factors
    vector<int> v;
    v.push_back(1);
 
    // note that this loop runs till sqrt(n)
    int sqrtN = sqrt(n);
    for (int i = 2; i <= sqrtN; i++) {
        // if the value of i is a factor
        if (n % i == 0) {
            v.push_back(i);
            // condition to check the
            // divisor is not the number itself
            if (n / i != i) {
                v.push_back(n / i);
            }
        }
    }
    // return the vector
    return v;
}
 
// Function to check if the
// number is semi-perfect or not
bool check(int n)
{
    vector<int> v;
 
    // find the divisors
    v = factors(n);
 
    // sorting the vector
    sort(v.begin(), v.end());
 
    int r = v.size();
 
    // initialize to store computations of subproblems
    vector<bool> subset(n + 1, false);
 
    // Base Case
    subset[0] = true;
 
    // iterate over subproblems to get the current
    // value from previous computations
    for (int i = 0; i < r; i++) {
        for (int j = n; j >= v[i]; j--) {
            subset[j] = subset[j] || subset[j - v[i]];
        }
    }
 
    // return final answer
    return subset[n];
}
 
// Driver Code
int main()
{
    int n = 40;
 
    if (check(n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

import java.util.ArrayList;
import java.util.Collections;
 
public class Main {
 
    // Function to find all the factors of the number excluding the number itself
    static ArrayList<Integer> factors(int n) {
        // ArrayList to store the factors
        ArrayList<Integer> v = new ArrayList<>();
        v.add(1);
 
        // Note that this loop runs till sqrt(n)
        int sqrtN = (int) Math.sqrt(n);
        for (int i = 2; i <= sqrtN; i++) {
            // If the value of i is a factor
            if (n % i == 0) {
                v.add(i);
                // Condition to check the divisor is not the number itself
                if (n / i != i) {
                    v.add(n / i);
                }
            }
        }
 
        // Return the ArrayList of factors
        return v;
    }
 
    // Function to check if the number is semi-perfect or not
    static boolean check(int n) {
        ArrayList<Integer> v;
 
        // Find the divisors
        v = factors(n);
 
        // Sorting the ArrayList
        Collections.sort(v);
 
        int r = v.size();
 
        // Initialize an array to store computations of subproblems
        boolean[] subset = new boolean[n + 1];
 
        // Base Case
        subset[0] = true;
 
        // Iterate over subproblems to get the current
        // value from previous computations
        for (int i = 0; i < r; i++) {
            for (int j = n; j >= v.get(i); j--) {
                subset[j] = subset[j] || subset[j - v.get(i)];
            }
        }
 
        // Return the final answer
        return subset[n];
    }
 
    // Driver Code
    public static void main(String[] args) {
        int n = 40;
 
        if (check(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Python3

import math
 
# Function to find all the factors of
# the number excluding the number itself
def factors(n):
    # List to store the factors
    v = [1]
 
    # Note that this loop runs till sqrt(n)
    sqrtN = int(math.sqrt(n))
    for i in range(2, sqrtN + 1):
        # If the value of i is a factor
        if n % i == 0:
            v.append(i)
            # Condition to check the
            # divisor is not the number itself
            if n // i != i:
                v.append(n // i)
    # Return the list
    return v
 
# Function to check if the
# number is semi-perfect or not
def check(n):
    v = []
 
    # Find the divisors
    v = factors(n)
 
    # Sorting the list
    v.sort()
 
    r = len(v)
 
    # Initialize to store computations of subproblems
    subset = [False] * (n + 1)
 
    # Base Case
    subset[0] = True
 
    # Iterate over subproblems to get the current
    # value from previous computations
    for i in range(r):
        for j in range(n, v[i] - 1, -1):
            subset[j] = subset[j] or subset[j - v[i]]
 
    # Return final answer
    return subset[n]
 
# Driver Code
if __name__ == "__main__":
    n = 40
 
    if check(n):
        print("Yes")
    else:
        print("No")

C#

using System;
using System.Collections.Generic;
 
class Program
{
    // Function to find all the factors of the number excluding the number itself
    static List<int> Factors(int n)
    {
        // List to store the factors
        List<int> factorsList = new List<int>();
        factorsList.Add(1);
 
        // Note that this loop runs until sqrt(n)
        int sqrtN = (int)Math.Sqrt(n);
        for (int i = 2; i <= sqrtN; i++)
        {
            // If the value of i is a factor
            if (n % i == 0)
            {
                factorsList.Add(i);
                // Condition to check that the divisor is not the number itself
                if (n / i != i)
                {
                    factorsList.Add(n / i);
                }
            }
        }
        // Return the list
        return factorsList;
    }
 
    // Function to check if the number is semi-perfect or not
    static bool CheckSemiPerfect(int n)
    {
        List<int> factorsList = new List<int>();
 
        // Find the divisors
        factorsList = Factors(n);
 
        // Sorting the list
        factorsList.Sort();
 
        int r = factorsList.Count;
 
        // Initialize an array to store computations of subproblems
        bool[] subset = new bool[n + 1];
 
        // Base Case
        subset[0] = true;
 
        // Iterate over subproblems to get the current value from previous computations
        for (int i = 0; i < r; i++)
        {
            for (int j = n; j >= factorsList[i]; j--)
            {
                subset[j] = subset[j] || subset[j - factorsList[i]];
            }
        }
 
        // Return the final answer
        return subset[n];
    }
 
    // Driver Code
    static void Main()
    {
        int n = 40;
 
        if (CheckSemiPerfect(n))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed by shivamgupta0987654321

Javascript

// Function to find all the factors of a number excluding the number itself
function factors(n) {
    const v = [1]; // Array to store the factors
    const sqrtN = Math.sqrt(n);
 
    for (let i = 2; i <= sqrtN; i++) {
        // If i is a factor
        if (n % i === 0) {
            v.push(i);
            // Check if the divisor is not the number itself
            if (n / i !== i) {
                v.push(n / i);
            }
        }
    }
    // Return the array of factors
    return v;
}
 
// Function to check if the number is semi-perfect or not
function check(n) {
    let v = [];
 
    // Find the divisors
    v = factors(n);
 
    // Sort the array
    v.sort((a, b) => a - b);
 
    const r = v.length;
 
    // Initialize an array to store computations of subproblems
    const subset = Array(n + 1).fill(false);
 
    // Base Case
    subset[0] = true;
 
    // Iterate over subproblems to get the current
    // value from previous computations
    for (let i = 0; i < r; i++) {
        for (let j = n; j >= v[i]; j--) {
            subset[j] = subset[j] || subset[j - v[i]];
        }
    }
 
    // Return the final answer
    return subset[n];
}
 
// Driver Code
const n = 40;
 
if (check(n)) {
    console.log("Yes");
} else {
    console.log("No");
}

Output

Yes

Time Complexity: O(number of factors * N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!