Una potencia perfecta es un número que se puede expresar como potencia de otro entero positivo.
Dado un número n, encuentra el número de números del 1 al n que son del tipo x y donde x >= 1 y y > 1
Ejemplos:
Input : n = 10 Output : 4 1 4 8 and 9 are the numbers that are of form x ^ y where x > 0 and y > 1 Input : n = 50 Output : 10
Una solución simple es pasar por todas las potencias de los números desde i = 2 hasta la raíz cuadrada de n.
C++
// CPP program to count number of numbers from
// 1 to n are of type x^y where x>0 and y>1
#include <bits/stdc++.h>
using namespace std;
// For our convenience
#define ll long long
// Function that keeps all the odd power
// numbers upto n
int powerNumbers(int n)
{
// v is going to store all power numbers
vector<int> v;
v.push_back(1);
// Traverse through all base numbers and
// compute all their powers smaller than
// or equal to n.
for (ll i = 2; i * i <= n; i++) {
ll j = i * i;
v.push_back(j);
while (j * i <= n) {
v.push_back(j * i);
j = j * i;
}
}
// Remove all duplicates
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
return v.size();
}
int main()
{
cout << powerNumbers(50);
return 0;
}
Java
// Java program to count number of numbers from
// 1 to n are of type x^y where x>0 and y>1
import java.io.*;
import java.util.*;
public class GFG {
// Function that keeps all the odd power
// numbers upto n
static int powerNumbers(int n)
{
// v is going to store all unique
// power numbers
HashSet<Integer> v = new HashSet<Integer>();
v.add(1);
// Traverse through all base numbers
// and compute all their powers
// smaller than or equal to n.
for (int i = 2; i * i <= n; i++) {
int j = i * i;
v.add(j);
while (j * i <= n) {
v.add(j * i);
j = j * i;
}
}
return v.size();
}
// Driver code
public static void main(String args[])
{
System.out.print(powerNumbers(50));
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
Python3
# Python3 program to count number # of numbers from 1 to n are of # type x^y where x>0 and y>1 # Function that keeps all the odd # power numbers upto n def powerNumbers(n): # v is going to store all # unique power numbers v = set(); v.add(1); # Traverse through all base # numbers and compute all # their powers smaller than # or equal to n. for i in range(2, n+1): if(i * i <= n): j = i * i; v.add(j); while (j * i <= n): v.add(j * i); j = j * i; return len(v); print (powerNumbers(50)); # This code is contributed by # Manish Shaw (manishshaw1)
C#
// C# program to count number of numbers from
// 1 to n are of type x^y where x>0 and y>1
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
// Function that keeps all the odd power
// numbers upto n
static int powerNumbers(int n)
{
// v is going to store all unique
// power numbers
HashSet<int> v = new HashSet<int>();
v.Add(1);
// Traverse through all base numbers
// and compute all their powers
// smaller than or equal to n.
for (int i = 2; i * i <= n; i++) {
int j = i * i;
v.Add(j);
while (j * i <= n) {
v.Add(j * i);
j = j * i;
}
}
return v.Count;
}
// Driver code
public static void Main()
{
Console.WriteLine(powerNumbers(50));
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
PHP
<?php
// PHP program to count number of
// numbers from 1 to n are of type
// x^y where x>0 and y>1
// Function that keeps all the
// odd power numbers upto n
function powerNumbers($n)
{
// v is going to store
// all power numbers
$v = array();
array_push($v, 1);
// Traverse through all base
// numbers and compute all
// their powers smaller than
// or equal to n.
for ($i = 2; $i * $i <= $n; $i++)
{
$j = $i * $i;
array_push($v, $j);
while ($j * $i <= $n)
{
array_push($v, $j * $i);
$j = $j * $i;
}
}
// Remove all duplicates
sort($v);
$v = array_unique($v);
return count($v);
}
// Driver Code
echo (powerNumbers(50));
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// JavaScript program to count number of numbers from
// 1 to n are of type x^y where x>0 and y>1
// Function that keeps all the odd power
// numbers upto n
function powerNumbers(n)
{
// v is going to store all unique
// power numbers
let v = new Set();
v.add(1);
// Traverse through all base numbers
// and compute all their powers
// smaller than or equal to n.
for (let i = 2; i * i <= n; i++) {
let j = i * i;
v.add(j);
while (j * i <= n) {
v.add(j * i);
j = j * i;
}
}
return v.size;
}
document.write(powerNumbers(50));
</script>
Producción:
10
Solución eficiente
Dividimos el conjunto de salida en subconjuntos.
Potencias pares: simplemente necesitamos hacer la raíz cuadrada de n . La cuenta de potencias pares menores que n es la raíz cuadrada de n. Por ejemplo, incluso las potencias menores que 25 son (1, 4, 9, 16 y 25).
Potencias impares: modificamos la función anterior para considerar solo potencias impares.
C++
// C++ program to count number of numbers from
// 1 to n are of type x^y where x>0 and y>1
#include <bits/stdc++.h>
using namespace std;
// For our convenience
#define ll long long
// Function that keeps all the odd power
// numbers upto n
int powerNumbers(int n)
{
vector<int> v;
for (ll i = 2; i * i * i <= n; i++) {
ll j = i * i;
while (j * i <= n) {
j *= i;
// We need exclude perfect
// squares.
ll s = sqrt(j);
if (s * s != j)
v.push_back(j);
}
}
// sort the vector
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
// Return sum of odd and even powers.
return v.size() + (ll)sqrt(n);
}
int main()
{
cout << powerNumbers(50);
return 0;
}
Java
// Java program to count number
// of numbers from 1 to n are
// of type x^y where x>0 and y>1
import java.io.*;
import java.util.*;
class GFG
{
// Function that keeps all
// the odd power numbers upto n
static long powerNumbers(int n)
{
HashSet<Long> v = new HashSet<Long>();
for (long i = 2; i * i * i <= n; i++)
{
long j = i * i;
while (j * i <= n)
{
j *= i;
// We need exclude
// perfect squares.
long s = (long)Math.sqrt(j);
if (s * s != j)
v.add(j);
}
}
// sort the vector
// v.Sort();
// v.erase(unique(v.begin(),
// v.end()), v.end());
// Return sum of odd
// and even powers.
return v.size() + (long)Math.sqrt(n);
}
// Driver Code
public static void main(String args[])
{
System.out.print(powerNumbers(50));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python3 program to count number of # numbers from 1 to n are of type x^y # where x>0 and y>1 import math # Function that keeps all the odd power # numbers upto n def powerNumbers( n): v = [] for i in range(2, int(math.pow(n, 1.0 / 3.0)) + 1) : j = i * i while (j * i <= n) : j = j * i # We need exclude perfect # squares. s = int(math.sqrt(j)) if (s * s != j): v.append(j) # sort the vector v.sort() v = list(dict.fromkeys(v)) # Return sum of odd and even powers. return len(v) + int(math.sqrt(n)) # Driver Code if __name__=='__main__': print (powerNumbers(50)) # This code is contributed by Arnab Kundu
C#
// C# program to count number
// of numbers from 1 to n are
// of type x^y where x>0 and y>1
using System;
using System.Collections.Generic;
class GFG
{
// Function that keeps all
// the odd power numbers upto n
static long powerNumbers(int n)
{
HashSet<long> v = new HashSet<long>();
for (long i = 2; i * i * i <= n; i++)
{
long j = i * i;
while (j * i <= n)
{
j *= i;
// We need exclude
// perfect squares.
long s = (long)Math.Sqrt(j);
if (s * s != j)
v.Add(j);
}
}
// sort the vector
//v.Sort();
//v.erase(unique(v.begin(),
// v.end()), v.end());
// Return sum of odd
// and even powers.
return v.Count + (long)Math.Sqrt(n);
}
// Driver Code
static void Main()
{
Console.Write(powerNumbers(50));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
PHP
<?php
// PHP program to count number
// of numbers from 1 to n are
// of type x^y where x>0 and y>1
// Function that keeps all the
// odd power numbers upto n
function powerNumbers($n)
{
$v = array();
for ($i = 2; $i * $i * $i <= $n; $i++)
{
$j = $i * $i;
while ($j * $i <= $n)
{
$j *= $i;
// We need exclude perfect
// squares.
$s = sqrt($j);
if ($s * $s != $j)
array_push($v, $j);
}
}
// sort the vector
sort($v);
$uni = array_unique($v);
for ($i = 0; $i < count($uni); $i++)
{
$key = array_search($uni[$i], $v);
unset($v[$key]);
}
// Return sum of odd
// and even powers.
return count($v) + 3 +
intval(sqrt($n));
}
// Driver Code
echo (powerNumbers(50));
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript program to count number
// of numbers from 1 to n are
// of type x^y where x>0 and y>1
// Function that keeps all
// the odd power numbers upto n
function powerNumbers(n)
{
let v = new Set();
for (let i = 2; i * i * i <= n; i++)
{
let j = i * i;
while (j * i <= n)
{
j *= i;
// We need exclude
// perfect squares.
let s = parseInt(Math.sqrt(j), 10);
if (s * s != j)
v.add(j);
}
}
// sort the vector
// v.Sort();
// v.erase(unique(v.begin(),
// v.end()), v.end());
// Return sum of odd
// and even powers.
return v.size + parseInt(Math.sqrt(n), 10);
}
document.write(powerNumbers(50));
// This code is contributed by vaibhavrabadiya3.
</script>
Producción :
10
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA