Dado un número par N , la tarea es comprobar si es un número perfecto o no sin encontrar sus divisores .
En teoría de números, un número par perfecto es un número entero positivo que es par o que es igual a la suma de sus divisores positivos, excluyendo el número en sí.
Un número par perfecto se puede representar como P * (P + 1) / 2 donde P es Mersenne Prime .
Un primo de Mersenne es un número primo de la forma 2 q – 1 donde q también es un número primo.
Por ejemplo: si N = 6,
si elegimos que q sea 2 (número primo), entonces primo de Mersenne (P) es 2 2 – 1 = 3.
Por lo tanto, el número par perfecto formado por la fórmula es 3 * (3 + 1 ) / 2 = 6.
Ejemplos:
Entrada: N = 6
Salida: Sí
Explicación:
El número entero 6 se puede escribir como 6 = 1 + 2 + 3. Por lo tanto, es un número perfecto.Entrada: N =156
Salida: No
Explicación:
El número entero 156 no se puede escribir como una suma de sus divisores. Por lo tanto, no es un número perfecto.
Acercarse:
- Encuentra la raíz cuadrada del número dado para obtener un número cercano a 2 q – 1 .
- Encuentre q-1 a partir de la raíz cuadrada del número y luego verifique si 2 q-1 * (2 q -1) da el número ingresado. Si no, entonces no es un número perfecto, de lo contrario continúa.
- Comprueba si q es primo o no . Si no es primo entonces 2 q -1 no puede ser primo y posteriormente comprobar si 2 q -1 es primo.
- Si todas las condiciones anteriores se cumplen, entonces es un número par perfecto, de lo contrario no lo es.
A continuación se muestra la implementación del enfoque anterior:
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 approach import 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>
Yes
Complejidad de Tiempo: O(N 1/4 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por debarpan_bose_chowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA