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!
