Contar enteros hasta N que sean iguales al menos a la 2ª potencia de cualquier entero superior a 1

Dado un entero positivo N , la tarea es contar el número de enteros del rango [1, N], que se pueden representar como a ^b , donde a y b son enteros mayores que 1 .

Ejemplos:

Entrada: N = 6
Salida: 1
Explicación:
Solo ese entero del rango [1, 6] es 4 (= 2 ² ).
Por lo tanto, el conteo requerido es 1.

Entrada: N = 10
Salida: 3

Enfoque: El problema dado se puede resolver contando todos los posibles pares de elementos (a, b) tales que a ^b sea como máximo N . Siga los pasos a continuación para resolver el problema:

• Inicialice un HashSet para almacenar todos los valores posibles de a ^b , que es como máximo N.
• Iterar sobre el rango [2, √N] , y para cada valor de a , inserte todos los valores posibles de a ^b que tengan un valor máximo de N, donde b se encuentra sobre el rango [1, N] .
• Después de completar los pasos anteriores, imprima el tamaño de HashSet como el recuento resultante de enteros.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the integers
// up to N that can be represented
// as a ^ b, where a &b > 1
void printNumberOfPairs(int N)
{
     
    // Initialize a HashSet
    unordered_set<int> st;
 
    // Iterating over the range
    // [2, sqrt(N)]
    for(int i = 2; i * i <= N; i++)
    {
        int x = i;
 
        // Generate all possible
        // power of x
        while (x <= N)
        {
             
            // Multiply x by i
            x *= i;
 
            // If the generated number
            // lies in the range [1, N]
            // then insert it in HashSet
            if (x <= N)
            {
                st.insert(x);
            }
        }
    }
 
    // Print the total count
    cout << st.size();
}
 
// Driver code
int main()
{
    int N = 10000;
    printNumberOfPairs(N);
 
    return 0;
}
 
// This code is contributed by Kingash

// Java program for the above approach
 
import java.util.HashSet;
 
public class GFG {
 
    // Function to count the integers
    // up to N that can be represented
    // as a ^ b, where a &b > 1
    static void printNumberOfPairs(int N)
    {
        // Initialize a HashSet
        HashSet<Integer> st
            = new HashSet<Integer>();
 
        // Iterating over the range
        // [2, sqrt(N)]
        for (int i = 2; i * i <= N; i++) {
 
            int x = i;
 
            // Generate all possible
            // power of x
            while (x <= N) {
 
                // Multiply x by i
                x *= i;
 
                // If the generated number
                // lies in the range [1, N]
                // then insert it in HashSet
                if (x <= N) {
                    st.add(x);
                }
            }
        }
 
        // Print the total count
        System.out.println(st.size());
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int N = 10000;
        printNumberOfPairs(N);
    }
}

# Python 3 program for the above approach
from math import sqrt
 
# Function to count the integers
# up to N that can be represented
# as a ^ b, where a &b > 1
def printNumberOfPairs(N):
   
    # Initialize a HashSet
    st = set()
 
    # Iterating over the range
    # [2, sqrt(N)]
    for i in range(2, int(sqrt(N)) + 1, 1):
        x = i
         
        # Generate all possible
        # power of x
        while(x <= N):
           
            # Multiply x by i
            x *= i
             
            # If the generated number
            # lies in the range [1, N]
            # then insert it in HashSet
            if (x <= N):
                st.add(x)
 
    # Print the total count
    print(len(st))
 
# Driver code
if __name__ == '__main__':
    N = 10000
    printNumberOfPairs(N)
     
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to count the integers
// up to N that can be represented
// as a ^ b, where a &b > 1
static void printNumberOfPairs(int N)
{
     
    // Initialize a HashSet
    HashSet<int> st = new HashSet<int>();
 
    // Iterating over the range
    // [2, sqrt(N)]
    for(int i = 2; i * i <= N; i++)
    {
        int x = i;
 
        // Generate all possible
        // power of x
        while (x <= N)
        {
             
            // Multiply x by i
            x *= i;
 
            // If the generated number
            // lies in the range [1, N]
            // then insert it in HashSet
            if (x <= N)
            {
                st.Add(x);
            }
        }
    }
 
    // Print the total count
    Console.WriteLine(st.Count);
}
 
// Driver Code
public static void Main(string[] args)
{
    int N = 10000;
    printNumberOfPairs(N);
}
}
 
// This code is contributed by ukasp

<script>
 
// Javascript program for the above approach
 
 
// Function to count the integers
// up to N that can be represented
// as a ^ b, where a &b > 1
function printNumberOfPairs( N)
{
    // Initialize a HashSet
    var st = new Set();
 
    // Iterating over the range
    // [2, sqrt(N)]
    for (let i = 2; i * i <= N; i++) {
 
        let x = i;
 
        // Generate all possible
        // power of x
        while (x <= N) {
 
            // Multiply x by i
            x *= i;
 
            // If the generated number
            // lies in the range [1, N]
            // then insert it in HashSet
            if (x <= N) {
                st.add(x);
            }
        }
    }
 
    // Print the total count
    document.write(st.size);
}
 
// Driver Code
 
let N = 10000;
printNumberOfPairs(N);
 
</script>

124

Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)