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 23 Input: n = 49 Output: true 49 can be expressed as 72 Input: n = 48 Output: false 48 can't be expressed as xy
La idea es simple probar todos los números x comenzando desde 2 hasta la raíz cuadrada de n (número dado). Para cada x, prueba con x^y donde y comienza desde 2 y aumenta uno por uno hasta que x^y se vuelve n o mayor que n.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to check if a given number can be expressed
// as power
#include <bits/stdc++.h>
using namespace std;
// Returns true if n can be written as x^y
bool isPower(unsigned n)
{
if (n==1) return true;
// Try all numbers from 2 to sqrt(n) as base
for (int x=2; x<=sqrt(n); x++)
{
unsigned y = 2;
unsigned p = pow(x, y);
// Keep increasing y while power 'p' is smaller
// than n.
while (p<=n && p>0)
{
if (p==n)
return true;
y++;
p = pow(x, y);
}
}
return false;
}
// Driver Program
int main()
{
for (int i =2; i<100; i++)
if (isPower(i))
cout << i << " ";
return 0;
}
Java
// Java code to check if a number can be expressed
// as x^y (x raised to power y)
class GFG {
// Returns true if n can be written as x^y
static boolean isPower(int n)
{
for (int x = 2; x <= Math.sqrt(n); x++) {
int y = 2;
double p = Math.pow(x, y);
while (p <= n && p > 0) {
if (p == n)
return true;
y++;
p = Math.pow(x, y);
}
}
return false;
}
// Driver function
public static void main(String[] args)
{
for (int i = 2; i < 100; i++)
if (isPower(i))
System.out.print(i + " ");
}
}
// This code is submitted by Kamal Rawal
Python3
# Python3 program to check if # a given number can be expressed # as power import math # Returns true if n can be written as x^y def isPower(n) : if (n==1) : return True # Try all numbers from 2 to sqrt(n) as base for x in range(2,(int)(math.sqrt(n))+1) : y = 2 p = (int)(math.pow(x, y)) # Keep increasing y while power 'p' is smaller # than n. while (p<=n and p>0) : if (p==n) : return True y = y + 1 p = math.pow(x, y) return False # Driver Program for i in range(2,100 ) : if (isPower(i)) : print(i,end=" ") # This code is contributed by Nikita Tiwari.
C#
// C# code to check if a number
// can be expressed as x^y
// (x raised to power y)
using System;
class GFG
{
// Returns true if n can
// be written as x^y
static bool isPower(int n)
{
for (int x = 2; x <= Math.Sqrt(n); x++)
{
int y = 2;
double p = Math.Pow(x, y);
while (p <= n && p > 0)
{
if (p == n)
return true;
y++;
p = Math.Pow(x, y);
}
}
return false;
}
// Driver Code
static public void Main ()
{
for (int i = 2; i < 100; i++)
if (isPower(i))
Console.Write(i + " ");
}
}
// This code is submitted by ajit.
PHP
<?php
// PHP program to check if a given
// number can be expressed as power
// Returns true if n can
// be written as x^y
function isPower($n)
{
if ($n == 1) return true;
// Try all numbers from 2
// to sqrt(n) as base
for ($x = 2; $x <= sqrt($n); $x++)
{
$y = 2;
$p = pow($x, $y);
// Keep increasing y while
// power 'p' is smaller than n.
while ($p <= $n && $p > 0)
{
if ($p == $n)
return true;
$y++;
$p = pow($x, $y);
}
}
return false;
}
// Driver Code
for ($i = 2; $i < 100; $i++)
if (isPower($i))
echo $i , " ";
// This code is contributed by aj_36
?>
Javascript
<script>
// javascript code to check if a number can be expressed
// as x^y (x raised to power y)
// Returns true if n can be written as x^y
function isPower(n)
{
for (x = 2; x <= Math.sqrt(n); x++) {
var y = 2;
var p = Math.pow(x, y);
while (p <= n && p > 0) {
if (p == n)
return true;
y++;
p = Math.pow(x, y);
}
}
return false;
}
// Driver function
for (i = 2; i < 100; i++)
if (isPower(i))
document.write(i + " ");
// This code is contributed by gauravrajput1
</script>
Producción :
4 8 9 16 25 27 32 36 49 64 81
Una optimización en la solución anterior es evitar la llamada a pow() multiplicando p con x uno por uno.
C++
// C++ program to check if a given number can be expressed
// as power
#include <bits/stdc++.h>
using namespace std;
// Returns true if n can be written as x^y
bool isPower(unsigned int n)
{
// Base case
if (n <= 1) return true;
// Try all numbers from 2 to sqrt(n) as base
for (int x=2; x<=sqrt(n); x++)
{
unsigned p = x;
// Keep multiplying p with x while is smaller
// than or equal to x
while (p <= n)
{
p *= x;
if (p == n)
return true;
}
}
return false;
}
// Driver Program
int main()
{
for (int i =2; i<100; i++)
if (isPower(i))
cout << i << " ";
return 0;
}
Java
// Java code to check if a number can be expressed
// as x^y (x raised to power y)
class GFG {
// Returns true if n can be written as x^y
static boolean isPower(int n)
{
for (int x = 2; x <= Math.sqrt(n); x++) {
int p = x;
while (p <= n) {
p = p * x;
if (p == n)
return true;
}
}
return false;
}
// Driver function
public static void main(String[] args)
{
for (int i = 2; i < 100; i++)
if (isPower(i))
System.out.print(i + " ");
}
}
// This code is submitted by Kamal Rawal
Python3
# Python3 program to check if # a given number can be expressed # as power import math # Returns true if n can be written # as x ^ y def isPower(n) : # Base case if (n <= 1) : return True # Try all numbers from 2 to sqrt(n) # as base for x in range(2, (int)(math.sqrt(n)) + 1) : p = x # Keep multiplying p with x while # is smaller than or equal to x while (p <= n) : p = p * x if (p == n) : return True return False # Driver Program for i in range(2, 100) : if (isPower(i)) : print( i, end =" ") # This code is contributed by Nikita Tiwari.
C#
// C# code to check if a number
// can be expressed as x^y (x
// raised to power y)
using System;
class GFG
{
// Returns true if n can
// be written as x^y
static bool isPower(int n)
{
for (int x = 2;
x <= Math.Sqrt(n); x++)
{
int p = x;
while (p <= n)
{
p = p * x;
if (p == n)
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 submitted by nitin mittal.
PHP
<?php
// PHP program to check if a
// given number can be expressed
// as power
// Returns true if n can
// be written as x^y
function isPower($n)
{
// Base case
if ($n <= 1) return true;
// Try all numbers from 2
// to sqrt(n) as base
for ($x = 2; $x <= sqrt($n); $x++)
{
$p = $x;
// Keep multiplying p with
// x while is smaller
// than or equal to x
while ($p <= $n)
{
$p *= $x;
if ($p == $n)
return true;
}
}
return false;
}
// Driver Code
for ($i = 2; $i < 100; $i++)
if (isPower($i))
echo $i , " ";
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript code to check if a number
// can be expressed as x^y (x
// raised to power y)
// Returns true if n can
// be written as x^y
function isPower(n)
{
for (let x = 2; x <= parseInt(Math.sqrt(n), 10); x++)
{
let p = x;
while (p <= n)
{
p = p * x;
if (p == n)
return true;
}
}
return false;
}
for (let i = 2; i < 100; i++)
if (isPower(i))
document.write(i + " ");
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
4 8 9 16 25 27 32 36 49 64 81
Complejidad de tiempo: O(100 * n*sqrt(n)), donde n es el número que va de 1 a 100
Espacio auxiliar: O(1), ya que no se requiere espacio adicional
Implementación alternativa:
C++
// C++ program to check if a given number can be expressed
// as power
#include <bits/stdc++.h>
using namespace std;
// Returns true if n can be written as x^y
bool isPower(unsigned n)
{
float p;
if (n <= 1)
return 1;
for (int i = 2; i <= sqrt(n); i++) {
p = log2(n) / log2(i);
if ((ceil(p) == floor(p)) && p > 1)
return true;
}
return false;
}
// Driver Program
int main()
{
for (int i = 2; i < 100; i++)
if (isPower(i))
cout << i << " ";
return 0;
}
Java
// Java program to check if a given
// number can be expressed as power
import java.io.*;
import java.lang.Math;
class GFG {
// Returns true if n can be written as x^y
static boolean isPower(int n)
{
double p;
if (n <= 1)
{
return true;
}
for(int i = 2; i <= Math.sqrt(n); i++)
{
p = Math.log(n) / Math.log(i);
if ((Math.ceil(p) == Math.floor(p)) && p > 1)
{
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 shubhamsingh10
Python3
# Python3 program to check if a given # number can be expressed as power import math # Returns true if n can be # written as x^y def isPower(n): p = 0 if (n <= 1): return 1 for i in range(2, (int)(math.sqrt(n)) + 1): p = math.log2(n) / math.log2(i) if ((math.ceil(p) == math.floor(p)) and p > 1): return 1 return 0 # Driver code for i in range(2, 100): if isPower(i): print(i, end = " ") # This code is contributed by sallagondaavinashreddy7
C#
// C# program to check if a given
// number can be expressed as power
using System;
class GFG{
// Returns true if n can be written as x^y
static bool isPower(int n)
{
double p;
if (n <= 1)
{
return true;
}
for(int i = 2; i <= Math.Sqrt(n); i++)
{
p = Math.Log(n) / Math.Log(i);
if ((Math.Ceiling(p) == Math.Floor(p)) && p > 1)
{
return true;
}
}
return false;
}
// Driver code
static public void Main ()
{
for(int i = 2; i < 100; i++)
{
if (isPower(i))
Console.Write(i + " ");
}
}
}
// This code is contributed by shubhamsingh10
Javascript
<script>
// Javascript program to check if a given
// number can be expressed as power
// Returns true if n can be written as x^y
function isPower(n)
{
let p;
if (n <= 1)
{
return true;
}
for(let i = 2; i <= parseInt(Math.sqrt(n), 10); i++)
{
p = (Math.log(n) / Math.log(i)).toFixed(14);
if ((Math.ceil(p) == Math.floor(p)) && (p > 1))
{
return true;
}
}
return false;
}
for(let i = 2; i < 100; i++)
{
if (isPower(i))
document.write(i + " ");
}
</script>
Producción:
4 8 9 16 25 27 32 36 49 64 81
Complejidad de tiempo: O(100 * sqrt(n)), donde n es el número que va de 1 a 100
Espacio auxiliar: O(1), ya que no se requiere espacio adicional
Solución eficiente: comprueba si un número se puede expresar como a^b | Conjunto 2
Este artículo es una contribución de Vaibhav Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA