Cuenta números hasta N que se pueden expresar como potencias de números primos

Dado un número entero N , la tarea es contar números del rango [1, N] que son la potencia de los números primos .

Ejemplos:

Entrada: N = 6
Salida: 3
Explicación:
Los números del rango [1, 6] que se pueden expresar como potencias de números primos son:
2 = 2 1
3 = 3 1
4 = 2 2
5 = 5 1

Entrada: N = 9
Salida: 7
Explicación:
Los números del rango [1, 9] que se pueden expresar como potencias de números primos son:
2 = 2 1
3 = 3 1
4 = 2 2
5 = 5 1
7 = 7 1
8 = 2 3
9 = 3 2

Planteamiento: El problema se puede resolver utilizando Tamiz de Eratóstenes .

  1. Inicialice una array primo[] de longitud N+1 usando la criba de Eratóstenes , en la que primo[i] = 1 significa que i es un número primo y primo[i] = 0 significa que i no es un número primo.
  2. Empuje todos los números primos en un vector , digamos v .
  3. Inicializa una variable, digamos ans,  para almacenar el conteo de las potencias de los números primos.
  4. Para cada número primo, digamos p en el vector v , realice las siguientes operaciones:
    • Inicialice una variable, digamos temp, igual a p .
    • Verifique si la temperatura es menor que N. Si es cierto, realice las siguientes operaciones:
      • Aumentar ans en 1 .
      • Actualizar temp = temp * p , la próxima potencia de p .
  5. Devuelve el conteo final como ans .

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number
// of powers of prime numbers upto N
int countPowerOfPrimes(int N)
{
 
    // Sieve array
    int prime[N + 1];
 
    // Sieve of Eratosthenes
 
    // Initialize all numbers as prime
    for (int i = 0; i <= N; i++)
        prime[i] = 1;
 
    // Mark 0 and 1 as non prime
    prime[0] = 0;
    prime[1] = 0;
 
    for (int i = 2; i * i <= N; i++) {
        // If a prime number is found
        if (prime[i] == 1) {
            // Mark all multiples
            // of i as non-prime
            for (int j = i * i;
                 j <= N; j += i) {
                prime[j] = 0;
            }
        }
    }
 
    // Stores all prime
    // numbers upto N
    vector<int> v;
 
    // Push all the primes into v
    for (int i = 2; i <= N; i++) {
        if (prime[i] == 1) {
            v.push_back(i);
        }
    }
 
    // Stores the count of
    // powers of primes up to N
    int ans = 0;
 
    // Iterator over every
    // prime number up to N
    for (auto p : v) {
        // Store p in temp
        int temp = p;
 
        // Iterate until temp exceeds n
        while (temp <= N) {
            // Increment ans by 1
            ans = ans + 1;
 
            // Update temp to
            // next power of p
            temp = temp * p;
        }
    }
 
    // Return ans as the final answer
    return ans;
}
 
// Driver Code
int main()
{
    // Given Input
    int n = 9;
 
    // Function call to count
    // the number of power of
    // primes in the range [1, N]
    cout << countPowerOfPrimes(n);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
     
// Function to count the number
// of powers of prime numbers upto N
static int countPowerOfPrimes(int N)
{
     
    // Sieve array
    int prime[] = new int[N + 1];
 
    // Sieve of Eratosthenes
 
    // Initialize all numbers as prime
    for(int i = 0; i <= N; i++)
        prime[i] = 1;
 
    // Mark 0 and 1 as non prime
    prime[0] = 0;
    prime[1] = 0;
 
    for(int i = 2; i * i <= N; i++)
    {
         
        // If a prime number is found
        if (prime[i] == 1)
        {
             
            // Mark all multiples
            // of i as non-prime
            for(int j = i * i;
                    j < N + 1;
                    j += i)
            {
                prime[j] = 0;
            }
        }
    }
     
    // Stores all prime
    // numbers upto N
    int v[] = new int[N + 1];
    int j = 0;
 
    // Push all the primes into v
    for(int i = 2; i < N + 1; i++)
    {
        if (prime[i] == 1)
        {
            v[j] = i;
            j += 1;
        }
    }
     
    // Stores the count of
    // powers of primes up to N
    int ans = 0;
 
    // Iterator over every
    // prime number up to N
    for(int k = 0; k < j; k++)
    {
         
        // Store v[k] in temp
        int temp = v[k];
 
        // Iterate until temp exceeds n
        while (temp <= N)
        {
             
            // Increment ans by 1
            ans = ans + 1;
 
            // Update temp to
            // next power of v[k]
            temp = temp * v[k];
        }
    }
 
    // Return ans as the final answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 9;
     
    // Function call to count
    // the number of power of
    // primes in the range [1, N]
    System.out.println(countPowerOfPrimes(n));
}
}
 
// This code is contributed by AnkThon

Python3

# Python3 program for the above approach
 
# Function to count the number
# of powers of prime numbers upto N
def countPowerOfPrimes(N):
 
    # Sieve array
    prime = [1] * (N + 1)
 
    # Mark 0 and 1 as non prime
    prime[0] = 0
    prime[1] = 0
 
    for i in range(2, N + 1):
        if i * i > N:
            break
         
        # If a prime number is found
        if (prime[i] == 1):
             
            # Mark all multiples
            # of i as non-prime
            for j in range(i * i, N + 1, i):
                prime[j] = 0
 
    # Stores all prime
    # numbers upto N
    v = []
 
    # Push all the primes into v
    for i in range(2, N + 1):
        if (prime[i] == 1):
            v.append(i)
 
    # Stores the count of
    # powers of primes up to N
    ans = 0
 
    # Iterator over every
    # prime number up to N
    for p in v:
         
        # Store p in temp
        temp = p
 
        # Iterate until temp exceeds n
        while (temp <= N):
             
            # Increment ans by 1
            ans = ans + 1
 
            # Update temp to
            # next power of p
            temp = temp * p
 
    # Return ans as the final answer
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    n = 9
 
    # Function call to count
    # the number of power of
    # primes in the range [1, N]
    print (countPowerOfPrimes(n))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count the number
// of powers of prime numbers upto N
static int countPowerOfPrimes(int N)
{
     
    // Sieve array
    int[] prime = new int[N + 1];
    int j;
 
    // Sieve of Eratosthenes
 
    // Initialize all numbers as prime
    for(int i = 0; i <= N; i++)
        prime[i] = 1;
 
    // Mark 0 and 1 as non prime
    prime[0] = 0;
    prime[1] = 0;
 
    for(int i = 2; i * i <= N; i++)
    {
         
        // If a prime number is found
        if (prime[i] == 1)
        {
             
            // Mark all multiples
            // of i as non-prime
            for(j = i * i;
                j < N + 1;
                j += i)
            {
                prime[j] = 0;
            }
        }
    }
     
    // Stores all prime
    // numbers upto N
    int[] v = new int[N + 1];
    j = 0;
 
    // Push all the primes into v
    for(int i = 2; i < N + 1; i++)
    {
        if (prime[i] == 1)
        {
            v[j] = i;
            j += 1;
        }
    }
     
    // Stores the count of
    // powers of primes up to N
    int ans = 0;
 
    // Iterator over every
    // prime number up to N
    for(int k = 0; k < j; k++)
    {
         
        // Store v[k] in temp
        int temp = v[k];
 
        // Iterate until temp exceeds n
        while (temp <= N)
        {
             
            // Increment ans by 1
            ans = ans + 1;
 
            // Update temp to
            // next power of v[k]
            temp = temp * v[k];
        }
    }
 
    // Return ans as the final answer
    return ans;
}
 
// Driver Code
public static void Main(string[] args)
{
    int n = 9;
     
    // Function call to count
    // the number of power of
    // primes in the range [1, N]
    Console.Write(countPowerOfPrimes(n));
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to count the number
// of powers of prime numbers upto N
    function countPowerOfPrimes(N) {
 
        // Sieve array
        var prime = Array(N + 1).fill(0);
 
        // Sieve of Eratosthenes
 
        // Initialize all numbers as prime
        for (i = 0; i <= N; i++)
            prime[i] = 1;
 
        // Mark 0 and 1 as non prime
        prime[0] = 0;
        prime[1] = 0;
 
        for (i = 2; i * i <= N; i++) {
 
            // If a prime number is found
            if (prime[i] == 1) {
 
                // Mark all multiples
                // of i as non-prime
                for (j = i * i; j < N + 1; j += i) {
                    prime[j] = 0;
                }
            }
        }
 
        // Stores all prime
        // numbers upto N
        var v = Array(N + 1).fill(0);
        var j = 0;
 
        // Push all the primes into v
        for (i = 2; i < N + 1; i++) {
            if (prime[i] == 1) {
                v[j] = i;
                j += 1;
            }
        }
 
        // Stores the count of
        // powers of primes up to N
        var ans = 0;
 
        // Iterator over every
        // prime number up to N
        for (k = 0; k < j; k++) {
 
            // Store v[k] in temp
            var temp = v[k];
 
            // Iterate until temp exceeds n
            while (temp <= N) {
 
                // Increment ans by 1
                ans = ans + 1;
 
                // Update temp to
                // next power of v[k]
                temp = temp * v[k];
            }
        }
 
        // Return ans as the final answer
        return ans;
    }
 
    // Driver Code
     
        var n = 9;
 
        // Function call to count
        // the number of power of
        // primes in the range [1, N]
        document.write(countPowerOfPrimes(n));
 
// This code contributed by aashish1995
 
</script>
Producción: 

7

 

Complejidad de tiempo: O(N log (log N))
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por ujjwalmittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *