Dado un entero N, con factorización prima n1 p1 * n2 p2 …… La tarea es verificar si el entero N está aislado de potencia o no.
Se dice que un entero está aislado de potencia si n1 * p1 * n2 * p2 ….. = N .
Ejemplos :
Input: N = 12 Output: Power-isolated Integer. Input: N = 18 Output: Not a power-isolated integer.
Enfoque: para que un número entero esté aislado en potencia, el producto de sus factores primos y su potencia es igual al número entero. Entonces, para calcular lo mismo, debe encontrar todos los factores primos del número entero dado y sus respectivas potencias también. Luego, calcule su producto y verifique si el producto es igual al número entero o no.
Algoritmo:
- Encuentre el factor primo con su factor y guárdelos en un par clave-valor.
- Luego calcula el producto de todos los factores y sus potencias.
- si el producto es igual a un entero, imprime verdadero, de lo contrario, es falso.
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ program to find whether a number
// is power-isolated or not
#include <bits/stdc++.h>
using namespace std;
void checkIfPowerIsolated(int num)
{
int input = num;
int count = 0;
int factor[num + 1]={0};
// for 2 as prime factor
if(num % 2 == 0)
{
while(num % 2 == 0)
{
++count;
num/=2;
}
factor[2] = count;
}
// for odd prime factor
for (int i = 3; i*i <= num; i += 2)
{
count = 0;
while(num % i == 0)
{
++count;
num /= i;
}
if(count > 0)
factor[i] = count;
}
if(num > 1)
factor[num] = 1;
// calculate product of powers and prime factors
int product = 1;
for(int i = 0; i < num + 1; i++)
{
if(factor[i] > 0)
product = product * factor[i] * i;
}
// check result for power-isolation
if (product == input)
cout << "Power-isolated Integer\n";
else
cout << "Not a Power-isolated Integer\n";
}
// Driver code
int main()
{
checkIfPowerIsolated(12);
checkIfPowerIsolated(18);
checkIfPowerIsolated(35);
return 0;
}
// This code is contributed by mits
Java
// Java program to find whether a number
// is power-isolated or not
class GFG
{
static void checkIfPowerIsolated(int num)
{
int input = num;
int count = 0;
int[] factor= new int[num+1];
// for 2 as prime factor
if(num % 2 == 0)
{
while(num % 2 == 0)
{
++count;
num/=2;
}
factor[2] = count;
}
// for odd prime factor
for (int i = 3; i*i <= num; i += 2)
{
count = 0;
while(num % i == 0)
{
++count;
num /= i;
}
if(count > 0)
factor[i] = count;
}
if(num > 1)
factor[num] = 1;
// calculate product of powers and prime factors
int product = 1;
for(int i = 0; i < num + 1; i++)
{
if(factor[i] > 0)
product = product * factor[i] * i;
}
// check result for power-isolation
if (product == input)
System.out.print("Power-isolated Integer\n");
else
System.out.print("Not a Power-isolated Integer\n");
}
// Driver code
public static void main(String[] args)
{
checkIfPowerIsolated(12);
checkIfPowerIsolated(18);
checkIfPowerIsolated(35);
}
}
// This code is contributed by Code_Mech.
Python3
# Python3 program to find whether a number
# is power-isolated or not
def checkIfPowerIsolated(num):
input1 = num;
count = 0;
factor = [0] * (num + 1);
# for 2 as prime factor
if(num % 2 == 0):
while(num % 2 == 0):
count += 1;
num //= 2;
factor[2] = count;
# for odd prime factor
i = 3;
while(i * i <= num):
count = 0;
while(num % i == 0):
count += 1;
num //= i;
if(count > 0):
factor[i] = count;
i += 2;
if(num > 1):
factor[num] = 1;
# calculate product of powers and prime factors
product = 1;
for i in range(0, len(factor)):
if(factor[i] > 0):
product = product * factor[i] * i;
# check result for power-isolation
if (product == input1):
print("Power-isolated Integer");
else:
print("Not a Power-isolated Integer");
# Driver code
checkIfPowerIsolated(12);
checkIfPowerIsolated(18);
checkIfPowerIsolated(35);
# This code is contributed by mits
C#
// C# program to find whether a number
// is power-isolated or not
using System;
class GFG
{
static void checkIfPowerIsolated(int num)
{
int input = num;
int count = 0;
int[] factor= new int[num+1];
// for 2 as prime factor
if(num % 2 == 0)
{
while(num % 2 == 0)
{
++count;
num/=2;
}
factor[2] = count;
}
// for odd prime factor
for (int i = 3; i*i <= num; i += 2)
{
count = 0;
while(num % i == 0)
{
++count;
num /= i;
}
if(count > 0)
factor[i] = count;
}
if(num > 1)
factor[num] = 1;
// calculate product of powers and prime factors
int product = 1;
for(int i = 0; i < num + 1; i++)
{
if(factor[i] > 0)
product = product * factor[i] * i;
}
// check result for power-isolation
if (product == input)
Console.Write("Power-isolated Integer\n");
else
Console.Write("Not a Power-isolated Integer\n");
}
// Driver code
static void Main()
{
checkIfPowerIsolated(12);
checkIfPowerIsolated(18);
checkIfPowerIsolated(35);
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to find whether a number
// is power-isolated or not
function checkIfPowerIsolated($num)
{
$input = $num;
$count = 0;
$factor= array();
// for 2 as prime factor
if($num%2==0)
{
while($num%2==0)
{
++$count;
$num/=2;
}
$factor[2] = $count;
}
// for odd prime factor
for ($i=3; $i*$i <= $num; $i+=2)
{
$count = 0;
while($num%$i==0)
{
++$count;
$num /= $i;
}
if($count)
$factor[$i] = $count;
}
if($num>1)
$factor[$num] = 1;
// calculate product of powers and prime factors
$product = 1;
foreach ($factor as $primefactor => $power) {
$product = $product * $primefactor * $power;
}
// check result for power-isolation
if ($product == $input)
print_r("Power-isolated Integer\n");
else
print_r("Not a Power-isolated Integer\n");
}
// driver code
checkIfPowerIsolated(12);
checkIfPowerIsolated(18);
checkIfPowerIsolated(35);
?>
Javascript
<script>
// Javascript program to find whether a number
// is power-isolated or not
function checkIfPowerIsolated(num)
{
let input = num;
let count = 0;
let factor = new Array(0);
// for 2 as prime factor
if(num % 2 == 0)
{
while(num % 2 == 0)
{
++count;
num/=2;
}
factor[2] = count;
}
// for odd prime factor
for (let i = 3; i*i <= num; i += 2)
{
count = 0;
while(num % i == 0)
{
++count;
num /= i;
}
if(count > 0)
factor[i] = count;
}
if(num > 1)
factor[num] = 1;
// calculate product of powers and prime factors
let product = 1;
for(let i = 0; i < num + 1; i++)
{
if(factor[i] > 0)
product = product * factor[i] * i;
}
// check result for power-isolation
if (product == input)
document.write("Power-isolated Integer" + "<br>");
else
document.write("Not a Power-isolated Integer" + "<br>");
}
// Driver code
checkIfPowerIsolated(12);
checkIfPowerIsolated(18);
checkIfPowerIsolated(35);
// This code is contributed by Mayank Tyagi
</script>
Producción:
Power-isolated Integer Not a Power-isolated Integer Power-isolated Integer
Complejidad de tiempo: O(num)
Espacio Auxiliar: O(num)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA