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