A number N is said to be Multiply-perfect numbers if N divides sigma(N), where sigma(N) = sum of all divisors of N.
The first few Multiply-perfect numbers are:
1, 6, 28, 120, 496, 672, ……..
Check if N is a Multiply-perfect number
Given a number N, the task is to find if this number is Multiply-perfect number or not.
Examples:
Input: N = 120
Output: YES
Explanation:
Sum of 120’s divisors is 1 + 2 + 3 + 4 + 5 + 6 + 8 + 10 + 12 + 15 + 20 + 24 + 30 + 40 + 60 + 120 = 360 and 120 divides 360.
Therefore, 120 is a Multiply-perfect number.
Input: N = 32
Output: No
Approach: For a number N to be Multiply-perfect number, the following condition should hold true: sigma(N) % N = 0, where sigma(N) = sum of all divisors of N. Therefore, we will find sum of all divisors of N and check if it is divisible by N or not. If divisible print “Yes” else print “No.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the// sum of divisorsint getSum(int n){ int sum = 0; // Note that this loop // runs till square root of N for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // take only one of them if (n / i == i) sum = sum + i; // Otherwise take both else { sum = sum + i; sum = sum + (n / i); } } } return sum;}// Function to check Multiply-perfect numberbool MultiplyPerfectNumber(int n){ if (getSum(n) % n == 0) return true; else return false;}// Driver codeint main(){ int n = 28; if (MultiplyPerfectNumber(n)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
// Java implementation of the above approachclass GFG{ // Function to find the// sum of divisorsstatic int getSum(int n){ int sum = 0; // Note that this loop // runs till square root of N for(int i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // take only one of them if (n / i == i) sum = sum + i; // Otherwise take both else { sum = sum + i; sum = sum + (n / i); } } } return sum;}// Function to check Multiply-perfect numberstatic boolean MultiplyPerfectNumber(int n){ if (getSum(n) % n == 0) return true; else return false;}// Driver codepublic static void main(String[] args){ int n = 28; if (MultiplyPerfectNumber(n)) { System.out.print("Yes"); } else { System.out.print("No"); }}}// This code is contributed by Ritik Bansal |
Python3
# Python3 implementation of the above approachimport math# Function to find the# sum of divisorsdef getSum(n): sum1 = 0; # Note that this loop # runs till square root of N for i in range(1, int(math.sqrt(n))): if (n % i == 0): # If divisors are equal, # take only one of them if (n // i == i): sum1 = sum1 + i; # Otherwise take both else: sum1 = sum1 + i; sum1 = sum1 + (n // i); return sum1;# Function to check Multiply-perfect numberdef MultiplyPerfectNumber(n): if (getSum(n) % n == 0): return True; else: return False;# Driver coden = 28;if (MultiplyPerfectNumber(n)): print("Yes");else: print("No");# This code is contributed by Code_Mech |
C#
// C# implementation of the above approachusing System;class GFG{ // Function to find the// sum of divisorsstatic int getSum(int n){ int sum = 0; // Note that this loop // runs till square root of N for(int i = 1; i <= Math.Sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // take only one of them if (n / i == i) sum = sum + i; // Otherwise take both else { sum = sum + i; sum = sum + (n / i); } } } return sum;}// Function to check Multiply-perfect numberstatic bool MultiplyPerfectNumber(int n){ if (getSum(n) % n == 0) return true; else return false;}// Driver codepublic static void Main(){ int n = 28; if (MultiplyPerfectNumber(n)) { Console.Write("Yes"); } else { Console.Write("No"); }}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript implementation of the above approach // Function to find the // sum of divisors function getSum( n) { let sum = 0; // Note that this loop // runs till square root of N for ( i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // take only one of them if (n / i == i) sum = sum + i; // Otherwise take both else { sum = sum + i; sum = sum + (n / i); } } } return sum; } // Function to check Multiply-perfect number function MultiplyPerfectNumber( n) { if (getSum(n) % n == 0) return true; else return false; } // Driver code let n = 28; if (MultiplyPerfectNumber(n)) { document.write("Yes"); } else { document.write("No"); }// This code is contributed by Rajput-Ji</script> |
Output:
Yes
Time Complexity: O(N1/2)
Auxiliary Space: O(1)
References: https://en.wikipedia.org/wiki/Multiply_perfect_number
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
