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 1Entrada: 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 .
- 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.
- Empuje todos los números primos en un vector , digamos v .
- Inicializa una variable, digamos ans, para almacenar el conteo de las potencias de los números primos.
- 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 .
- 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