Given an even number N, the task is to check whether it is a Perfect number or not without finding its divisors.
In number theory, an Even Perfect Number is a positive integer which is even or that is equal to the sum of its positive divisors, excluding the number itself.
An even perfect number can be represented as P * (P + 1) / 2 where P is Mersenne Prime.
A Mersenne Prime is a prime number of form 2q – 1 where q is also a prime number.
For example: if N = 6,Â
If we choose q to be 2 (prime number) then mersenne prime (P) is 22 – 1 = 3.Â
Therefore, the Even perfect number formed by the formula is 3 * (3 + 1) / 2 = 6.
Examples:
Input: N = 6
Output: Yes
Explanation:
The integer 6 can be written as  6 = 1 + 2 + 3. Hence, its perfect number.Input: N  =156
Output: No
Explanation:
The integer 156 cannot be written as a sum of its divisors. Hence, its not a perfect number.
Approach:Â
Â
- Find the square root of the given number to get a number close to 2q – 1.
- Find q-1 from the square root of the number and then check whether 2q-1 * (2q-1) gives the number entered. If not then it is not a perfect number, otherwise continue.
- Check whether q is prime or not. If it is not prime then 2q-1 cannot be prime and subsequently check whether 2q-1 is prime.
- If all the above conditions hold true then it is an even perfect number otherwise not.
Below is the implementation of the above approach:
Â
C++
// C++ program for the above approach #include<bits/stdc++.h> using namespace std; Â
bool isPrime(long n); Â
// Function to check for perfect number void check(long num) { Â Â Â Â Â Â Â Â Â // Find a number close to 2^q-1 Â Â Â Â long root = (long)sqrt(num); Â
    // Calculate q-1     long poww = (long)(log(root) / log(2)); Â
    // Condition of perfect number     if (num == (long)(pow(2, poww) *                     (pow(2, poww + 1) - 1)))     { Â
        // Check whether q is prime or not         if (isPrime(poww + 1))         {                          // Check whether 2^q - 1 is a             // prime number or not             if (isPrime((long)pow(2,                 poww + 1) - 1))                 cout << "Yes" << endl;             else                cout << "No" << endl;         }         else            cout << "No" << endl;     }     else        cout << "No" << endl; } Â
// Function to check for prime number bool isPrime(long n) { Â Â Â Â if (n <= 1) Â Â Â Â Â Â Â Â return false; Â
    // Check whether it is equal to 2 or 3     else if (n == 2 || n == 3)         return true; Â
    else    {                  // Check if it can be divided by 2         // and 3 then it is not prime number         if (n % 2 == 0 || n % 3 == 0)             return false; Â
        // Check whether the given number be         // divide by other prime numbers         for(long i = 5; i <= sqrt(n); i += 6)         {             if (n % i == 0 || n % (i + 2) == 0)                 return false;         }         return true;     } } Â
// Driver Code int main() { Â Â Â Â long num = 6; Â Â Â Â Â Â Â Â Â check(num); Â Â Â Â Â Â Â Â Â return 0; } Â
// This code is contributed by rutvik_56 |
Java
// Java program for the above approach Â
class GFG { Â
    // Function to check for perfect number     private static void check(long num)     {         // Find a number close to 2^q-1         long root = (long)Math.sqrt(num); Â
        // Calculate q-1         long pow             = (long)(Math.log(root)                     / Math.log(2)); Â
        // Condition of perfect number         if (num             == (long)(Math.pow(2, pow)                     * (Math.pow(2, pow + 1) - 1))) { Â
            // Check whether q is prime or not             if (isPrime(pow + 1)) { Â
                // Check whether 2^q - 1 is a                 // prime number or not                 if (isPrime(                         (long)Math.pow(                             2, pow + 1)                         - 1))                     System.out.println("Yes"); Â
                else                    System.out.println("No");             }             else                System.out.println("No");         }         else            System.out.println("No");     } Â
    // Function to check for prime number     public static boolean isPrime(long n)     {         if (n <= 1)             return false; Â
        // Check whether it is equal to 2 or 3         else if (n == 2 || n == 3)             return true; Â
        else {             // Check if it can be divided by 2             // and 3 then it is not prime number             if (n % 2 == 0 || n % 3 == 0)                 return false; Â
            // Check whether the given number be             // divide by other prime numbers             for (long i = 5;                 i <= Math.sqrt(n);                 i += 6) {                 if (n % i == 0                    || n % (i + 2) == 0)                     return false;             }             return true;         }     } Â
    // Driver code     public static void main(String args[])     {         long num = 6;         check(num);     } } |
Python3
# Python3 program for the above approachimport mathÂ
# Function to check for perfect number def check(num): Â Â Â Â Â Â Â Â Â # Find a number close to 2^q-1 Â Â Â Â root = (int)(math.sqrt(num))Â
    # Calculate q-1     poww = (int)(math.log(root) /                 math.log(2))Â
    # Condition of perfect number     if (num == (int)(pow(2, poww) *                    (pow(2, poww + 1) - 1))):Â
        # Check whether q is prime or not         if (isPrime(poww + 1)):                         # Check whether 2^q - 1 is a             # prime number or not             if (isPrime((int)(pow(2,                 poww + 1)) - 1)):                 print("Yes")             else:                print("No")                          else:            print("No")     else:        print("No") Â
# Function to check for prime number def isPrime(n): Â
    if (n <= 1):         return bool(False) Â
    # Check whether it is equal to 2 or 3     elif (n == 2 or n == 3):         return bool(True) Â
    else:                  # Check if it can be divided by 2         # and 3 then it is not prime number         if (n % 2 == 0 or n % 3 == 0):             return bool(False)Â
        # Check whether the given number be         # divide by other prime numbers         for i in range(5, sqrt(n + 1) + 1, 6):            if (n % i == 0 or n % (i + 2) == 0):                return bool(False)                         return bool(True) Â
# Driver Code        num = 6     check(num)Â
# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approach using System; using System.Collections.Generic; Â
class GFG{ Â
// Function to check for perfect number private static void check(long num) { Â Â Â Â Â Â Â Â Â // Find a number close to 2^q-1 Â Â Â Â long root = (long)Math.Sqrt(num); Â
    // Calculate q-1     long pow = (long)(Math.Log(root) /                     Math.Log(2)); Â
    // Condition of perfect number     if (num == (long)(Math.Pow(2, pow) *                     (Math.Pow(2, pow + 1) - 1)))     {                  // Check whether q is prime or not         if (isPrime(pow + 1))         { Â
            // Check whether 2^q - 1 is a             // prime number or not             if (isPrime((long)Math.Pow(2, pow + 1) - 1))                 Console.WriteLine("Yes"); Â
            else                Console.WriteLine("No");         }         else            Console.WriteLine("No");     }     else        Console.WriteLine("No"); } Â
// Function to check for prime number public static bool isPrime(long n) { Â Â Â Â if (n <= 1) Â Â Â Â Â Â Â Â return false; Â
    // Check whether it is equal to 2 or 3     else if (n == 2 || n == 3)         return true; Â
    else    {                  // Check if it can be divided by 2         // and 3 then it is not prime number         if (n % 2 == 0 || n % 3 == 0)             return false; Â
        // Check whether the given number be         // divide by other prime numbers         for(long i = 5;                 i <= Math.Sqrt(n);                 i += 6)         {             if (n % i == 0 || n % (i + 2) == 0)                 return false;         }         return true;     } } Â
// Driver code public static void Main(String []args) { Â Â Â Â long num = 6; Â Â Â Â check(num); } } Â
// This code is contributed by amal kumar choubey |
Javascript
<script>// JavaScript program for the above approachÂ
    // Function to check for perfect number     function check(num)     {         // Find a number close to 2^q-1         let root = Math.floor(Math.sqrt(num));            // Calculate q-1         let pow             = Math.floor(Math.log(root)                     / Math.log(2));            // Condition of perfect number         if (num             == Math.floor(Math.pow(2, pow)                     * (Math.pow(2, pow + 1) - 1))) {                // Check whether q is prime or not             if (isPrime(pow + 1)) {                    // Check whether 2^q - 1 is a                 // prime number or not                 if (isPrime(                         Math.floor(Math.pow(                             2, pow + 1) )                        - 1))                     document.write("Yes");                    else                    document.write("No");             }             else                document.write("No");         }         else            document.write("No");     }        // Function to check for prime number     function isPrime(n)     {         if (n <= 1)             return false;            // Check whether it is equal to 2 or 3         else if (n == 2 || n == 3)             return true;            else {             // Check if it can be divided by 2             // and 3 then it is not prime number             if (n % 2 == 0 || n % 3 == 0)                 return false;                // Check whether the given number be             // divide by other prime numbers             for (let i = 5;                 i <= Math.floor(Math.sqrt(n));                 i += 6) {                 if (n % i == 0                    || n % (i + 2) == 0)                     return false;             }             return true;         }     } Â
// Driver Code            let num = 6;     check(num);                   </script> |
Output:Â
Yes
Â
Time Complexity: O(N1/4)
Auxiliary Space: O(1)
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!
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/even-perfect-number/ […]