Given an integer N, the task is to count numbers from the range [1, N] which are the power of prime numbers.
Examples:
Input: N = 6
Output: 3
Explanation:
Numbers from the range [1, 6] that can be expressed as powers of prime numbers are:
2 = 21
3 = 31
4 = 22
5 = 51Input: N = 9
Output: 7
Explanation:
Numbers from the range [1, 9] that can be expressed as powers of prime numbers are:
2 = 21
3 = 31
4 = 22
5 = 51
7 = 71
8 = 23
9 = 32
Approach: The problem can be solved using Sieve of Eratosthenes.
- Initialize an array prime[] of length N+1 using Sieve of Eratosthenes, in which prime[i] = 1 means i is a prime number and prime[i] = 0 means i is not a prime number.
- Push all the prime numbers into a vector, say v.
- Initialize a variable, say ans, to store the count of the powers of primes.
- For each prime, say p in vector v, perform the following operations:
- Initialize a variable, say temp, equal to p.
- Check if the temp is less than N. If found to be true, then perform the following operations:
- Increase ans by 1.
- Update temp = temp * p, the next power of p.
- Return the final count as ans.
Below is the implementation of the above approach:
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> |
7
Time Complexity: O(N log (log N))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!