Comprueba si un número se puede expresar como x^y (x elevado a la potencia y)
Dado un entero positivo n, encuentra si se puede expresar como x^y donde y > 1 y x > 0. x e y son enteros.
Ejemplos:
Input: n = 8 Output: true 8 can be expressed as 2^3 Input: n = 49 Output: true 49 can be expressed as 7^2 Input: n = 48 Output: false 48 can't be expressed as x^y
Hemos discutido dos enfoques diferentes en la publicación a continuación.
Comprueba si un número se puede expresar como x^y (x elevado a la potencia y) .
La idea es encontrar Log n en diferentes bases desde 2 hasta la raíz cuadrada de n. Si Log n para una base se convierte en un número entero, el resultado es verdadero; de lo contrario, el resultado es falso.
C++
// CPP program to find if a number
// can be expressed as x raised to
// power y.
#include <bits/stdc++.h>
using namespace std;
bool isPower(unsigned int n)
{
// Find Log n in different bases
// and check if the value is an
// integer
for (int x=2; x<=sqrt(n); x++) {
float f = log(n) / log(x);
if ((f - (int)f) == 0.0)
return true;
}
return false;
}
// Driver code
int main()
{
for (int i = 2; i < 100; i++)
if (isPower(i))
cout << i << " ";
return 0;
}
Java
// Java program to find if a number
// can be expressed as x raised to
// power y.
class GFG {
static boolean isPower(int n)
{
// Find Log n in different
// bases and check if the
// value is an integer
for (int x = 2; x <=
(int)Math.sqrt(n); x++)
{
float f = (float)Math.log(n) /
(float) Math.log(x);
if ((f - (int)f) == 0.0)
return true;
}
return false;
}
// Driver code
public static void main(String args[])
{
for (int i = 2; i < 100; i++)
if (isPower(i))
System.out.print( i + " ");
}
}
// This code is contributed by Sam007
Python3
# Python3 program to find if a number # can be expressed as x raised to # power y. import math def isPower(n): # Find Log n in different # bases and check if the # value is an integer for x in range(2,int(math.sqrt(n)) + 1): f = math.log(n) / math.log(x); if ((f - int(f)) == 0.0): return True; return False; # Driver code for i in range(2, 100): if (isPower(i)): print(i, end = " "); # This code is contributed by mits
C#
// C# program to find if a number
// can be expressed as x raised to
// power y.
using System;
class GFG
{
static bool isPower(int n)
{
// Find Log n in different
// bases and check if the
// value is an integer
for (int x = 2;
x <= (int)Math.Sqrt(n); x++)
{
float f = (float)Math.Log(n) /
(float) Math.Log(x);
if ((f - (int)f) == 0.0)
return true;
}
return false;
}
// Driver Code
public static void Main()
{
for (int i = 2; i < 100; i++)
if (isPower(i))
Console.Write( i + " ");
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find if a number
// can be expressed as x raised to
// power y.
function isPower($n)
{
// Find Log n in different
// bases and check if the
// value is an integer
for ($x = 2; $x <= sqrt($n); $x++)
{
$f = log($n) / log($x);
if (($f - (int)$f) == 0.0)
return true;
}
return false;
}
// Driver code
for ($i = 2; $i < 100; $i++)
if (isPower((int)$i))
echo $i." ";
// This code is contributed by Sam007
?>
Javascript
<script>
// javascript program to find if a number
// can be expressed as x raised to
// power y.
function isPower(n) {
// Find Log n in different
// bases and check if the
// value is an integer
for (x = 2; x <= parseInt( Math.sqrt(n)); x++)
{
var f = Math.log(n) / Math.log(x);
if ((f - parseInt( f)) == 0.0)
return true;
}
return false;
}
// Driver code
for (i = 2; i < 100; i++)
if (isPower(i))
document.write(i + " ");
// This code contributed by Rajput-Ji
</script>
Producción:
4 8 9 16 25 27 32 36 49 64 81
Complejidad del tiempo : O(sqrt(N))
Espacio auxiliar: O (1), ya que no estamos usando ningún espacio adicional