número perfecto par

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:
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: 
 

  1. Encuentra la raíz cuadrada del número dado para obtener un número cercano a 2 q – 1 .
  2. 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.
  3. 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.
  4. 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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *