A number is a perfect number if is equal to sum of its proper divisors, that is, sum of its positive divisors excluding the number itself. Write a function to check if a given number is perfect or not.
Examples:
Input: n = 15 Output: false Divisors of 15 are 1, 3 and 5. Sum of divisors is 9 which is not equal to 15. Input: n = 6 Output: true Divisors of 6 are 1, 2 and 3. Sum of divisors is 6.
A Simple Solution is to go through every number from 1 to n-1 and check if it is a divisor. Maintain sum of all divisors. If sum becomes equal to n, then return true, else return false.
An Efficient Solution is to go through numbers till square root of n. If a number ‘i’ divides n, then add both ‘i’ and n/i to sum.
Below is the implementation of efficient solution.
C++
// C++ program to check if a given number is perfect// or not#include<iostream>using namespace std;// Returns true if n is perfectbool isPerfect(long long int n){ // To store sum of divisors long long int sum = 1; // Find all divisors and add them for (long long int i=2; i*i<=n; i++) { if (n%i==0) { if(i*i!=n) sum = sum + i + n/i; else sum=sum+i; } } // If sum of divisors is equal to // n, then n is a perfect number if (sum == n && n != 1) return true; return false;} // Driver programint main(){ cout << "Below are all perfect numbers till 10000\n"; for (int n =2; n<10000; n++) if (isPerfect(n)) cout << n << " is a perfect number\n"; return 0;} |
Java
// Java program to check if a given // number is perfect or notimport java.io.*;public class GFG{ // Returns true if n is perfectstatic boolean isPerfect(int n){ // To store sum of divisors int sum = 1; // Find all divisors and add them for (int i = 2; i * i <= n; i++) { if (n % i==0) { if(i * i != n) sum = sum + i + n / i; else sum = sum + i; } } // If sum of divisors is equal to // n, then n is a perfect number if (sum == n && n != 1) return true; return false;}// Driver programpublic static void main (String[] args){ System.out.println("Below are all perfect" + "numbers till 10000"); for (int n = 2; n < 10000; n++) if (isPerfect(n)) System.out.println( n + " is a perfect number");}}// This code is contributed by mits |
Python3
# Python3 code to check if a given # number is perfect or not# Returns true if n is perfectdef isPerfect( n ): # To store sum of divisors sum = 1 # Find all divisors and add them i = 2 while i * i <= n: if n % i == 0: sum = sum + i + n/i i += 1 # If sum of divisors is equal to # n, then n is a perfect number return (True if sum == n and n!=1 else False)# Driver programprint("Below are all perfect numbers till 10000")n = 2for n in range (10000): if isPerfect (n): print(n , " is a perfect number") # This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to check if a given // number is perfect or notclass GFG{ // Returns true if n is perfectstatic bool isPerfect(int n){ // To store sum of divisors int sum = 1; // Find all divisors and add them for (int i = 2; i * i <= n; i++) { if (n % i==0) { if(i * i != n) sum = sum + i + n / i; else sum = sum + i; } } // If sum of divisors is equal to // n, then n is a perfect number if (sum == n && n != 1) return true; return false;}// Driver programstatic void Main(){ System.Console.WriteLine("Below are all perfect" + "numbers till 10000"); for (int n = 2; n < 10000; n++) if (isPerfect(n)) System.Console.WriteLine( n + " is a perfect number");}}// This code is contributed by chandan_jnu |
PHP
<?php// PHP program to check if a given number // is perfect or not// Returns true if n is perfectfunction isPerfect($n){ // To store sum of divisors $sum = 1; // Find all divisors and add them for ($i = 2; $i * $i <= $n; $i++) { if ($n % $i == 0) { if($i * $i != $n) $sum = $sum + $i + (int)($n / $i); else $sum = $sum + $i; } } // If sum of divisors is equal to // n, then n is a perfect number if ($sum == $n && $n != 1) return true; return false;}// Driver Codeecho "Below are all perfect numbers till 10000\n";for ($n = 2; $n < 10000; $n++) if (isPerfect($n)) echo "$n is a perfect number\n";// This code is contributed by mits?> |
Javascript
<script>// Javascript program to check if a given number is perfect // or not // Returns true if n is perfect function isPerfect(n) { // To store sum of divisors sum = 1; // Find all divisors and add them for (let i=2; i*i<=n; i++) { if (n%i==0) { if(i*i!=n) sum = sum + i + n/i; else sum=sum+i; } } // If sum of divisors is equal to // n, then n is a perfect number if (sum == n && n != 1) return true; return false; } // Driver program document.write("Below are all perfect numbers till 10000" + "<br>"); for (let n =2; n<10000; n++) if (isPerfect(n)) document.write(n + " is a perfect number" + "<br>"); // This code is contributed by Mayank Tyagi</script> |
Output
Below are all perfect numbers till 10000 6 is a perfect number 28 is a perfect number 496 is a perfect number 8128 is a perfect number
Time Complexity: O(√n)
Auxiliary Space: O(1), since no extra space has been taken.
Below are some interesting facts about Perfect Numbers:
1) Every even perfect number is of the form 2p?1(2p ? 1) where 2p ? 1 is prime.
2) It is unknown whether there are any odd perfect numbers.
References:
https://en.wikipedia.org/wiki/Perfect_number
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
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!
