Count numbers in a given range whose count of prime factors is a Prime Number
Given a 2D array Q[][] of size N * 2 representing queries of the form {L, R}. For each query, the task is to print the count of numbers in the range [L, R] with a count of prime factors equal to a prime number.
Examples:
Input: Q[][] = {{4, 8}, {30, 32}}
Output: 3 2
Explanation:
Query 1:
Prime factors of 4 = {2, 2} and count of prime factors = 2
Prime factors of 5 = {5} and count of prime factors = 1
Prime factors of 6 = {2, 3} and count of prime factors = 2
Prime factors of 7 = {7} and count of prime factors = 1
Prime factors of 8 = {2, 2, 2} and count of prime factors = 3
Therefore, the total count of numbers in the range [4, 8] having count of prime factors is a prime number is 3.
Query 2:
Prime factors of 30 = {2, 3, 5} and count of prime factors = 3
Prime factors of 31 = {31} and count of prime factors = 1
Prime factors of 32 = {2, 2, 2, 2, 2} and count of prime factors = 5
Therefore, the total count of numbers in the range [4, 8] having count of prime factors is a prime number is 2.Input: Q[][] = {{7, 12}, {10, 99}}
Output: 4
Naive Approach: The simplest approach to solve this problem is to traverse all the numbers in the range [L, R], and for each number, check if the count of prime factors of the number is a prime number or not. If found to be true, increment the counter by 1. After traversing, print the value of counter for each query.
Time Complexity: O(|Q| * (max(arr[i][1] – arr[i][0] + 1)) * sqrt(max(arr[i][1]))
Auxiliary space: O (1)
Efficient Approach: To optimize the above approach the idea is to precompute the smallest prime factor of each number in the range [Li, Ri] using Sieve of Eratosthenes. Follow the steps below to solve the problem:
- Generate and store the smallest prime factor of each element using Sieve of Eratosthenes.
- Find the count of prime factors for each number in the range [Li, Ri] using the Sieve.
- For each number, check if the total count of prime factors is a prime number or not. If found to be true then increment the counter.
- Create a prefix sum array, say sum[], where sum[i] will store the sum of elements from the range [0, i] whose count of prime factors is a prime number.
- Finally, for each query, print the value sum[arr[i][1]] – sum[arr[i][0] – 1].
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; #define MAX 1001 // Function to find the smallest prime factor // of all the numbers in range [0, MAX] vector< int > sieve() { // Stores smallest prime factor of all // the numbers in the range [0, MAX] vector< int > spf(MAX); // No smallest prime factor of // 0 and 1 exists spf[0] = spf[1] = -1; // Traverse all the numbers // in the range [1, MAX] for ( int i = 2; i < MAX; i++) { // Update spf[i] spf[i] = i; } // Update all the numbers whose // smallest prime factor is 2 for ( int i = 4; i < MAX; i = i + 2) { spf[i] = 2; } // Traverse all the numbers in // the range [1, sqrt(MAX)] for ( int i = 3; i * i < MAX; i++) { // Check if i is a prime number if (spf[i] == i) { // Update all the numbers whose // smallest prime factor is i for ( int j = i * i; j < MAX; j = j + i) { // Check if j is // a prime number if (spf[j] == j) { spf[j] = i; } } } } return spf; } // Function to find count of // prime factor of num int countFactors(vector< int >& spf, int num) { // Stores count of // prime factor of num int count = 0; // Calculate count of // prime factor while (num > 1) { // Update count count++; // Update num num = num / spf[num]; } return count; } // Function to precalculate the count of // numbers in the range [0, i] whose count // of prime factors is a prime number vector< int > precalculateSum(vector< int >& spf) { // Stores the sum of all the numbers // in the range[0, i] count of // prime factor is a prime number vector< int > sum(MAX); // Update sum[0] sum[0] = 0; // Traverse all the numbers in // the range [1, MAX] for ( int i = 1; i < MAX; i++) { // Stores count of prime factor of i int prime_factor = countFactors(spf, i); // If count of prime factor is // a prime number if (spf[prime_factor] == prime_factor) { // Update sum[i] sum[i] = sum[i - 1] + 1; } else { // Update sum[i] sum[i] = sum[i - 1]; } } return sum; } // Driver Code int main() { // Stores smallest prime factor of all // the numbers in the range [0, MAX] vector< int > spf = sieve(); // Stores the sum of all the numbers // in the range[0, i] count of // prime factor is a prime number vector< int > sum = precalculateSum(spf); int Q[][2] = { { 4, 8 }, { 30, 32 } }; // int N = sizeof(Q) / sizeof(Q[0]); for ( int i = 0; i < 2; i++) { cout << (sum[Q[i][1]] - sum[Q[i][0] - 1]) << " " ; } return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ public static int MAX = 1001 ; // Function to find the smallest prime factor // of all the numbers in range [0, MAX] public static int [] sieve() { // Stores smallest prime factor of all // the numbers in the range [0, MAX] int spf[] = new int [MAX]; // No smallest prime factor of // 0 and 1 exists spf[ 0 ] = spf[ 1 ] = - 1 ; // Traverse all the numbers // in the range [1, MAX] for ( int i = 2 ; i < MAX; i++) { // Update spf[i] spf[i] = i; } // Update all the numbers whose // smallest prime factor is 2 for ( int i = 4 ; i < MAX; i = i + 2 ) { spf[i] = 2 ; } // Traverse all the numbers in // the range [1, sqrt(MAX)] for ( int i = 3 ; i * i < MAX; i++) { // Check if i is a prime number if (spf[i] == i) { // Update all the numbers whose // smallest prime factor is i for ( int j = i * i; j < MAX; j = j + i) { // Check if j is // a prime number if (spf[j] == j) { spf[j] = i; } } } } return spf; } // Function to find count of // prime factor of num public static int countFactors( int spf[], int num) { // Stores count of // prime factor of num int count = 0 ; // Calculate count of // prime factor while (num > 1 ) { // Update count count++; // Update num num = num / spf[num]; } return count; } // Function to precalculate the count of // numbers in the range [0, i] whose count // of prime factors is a prime number public static int [] precalculateSum( int spf[]) { // Stores the sum of all the numbers // in the range[0, i] count of // prime factor is a prime number int sum[] = new int [MAX]; // Update sum[0] sum[ 0 ] = 0 ; // Traverse all the numbers in // the range [1, MAX] for ( int i = 1 ; i < MAX; i++) { // Stores count of prime factor of i int prime_factor = countFactors(spf, i); // If count of prime factor is // a prime number if (spf[prime_factor] == prime_factor) { // Update sum[i] sum[i] = sum[i - 1 ] + 1 ; } else { // Update sum[i] sum[i] = sum[i - 1 ]; } } return sum; } // Driver code public static void main(String[] args) { // Stores smallest prime factor of all // the numbers in the range [0, MAX] int spf[] = sieve(); // Stores the sum of all the numbers // in the range[0, i] count of // prime factor is a prime number int sum[] = precalculateSum(spf); int Q[][] = { { 4 , 8 }, { 30 , 32 } }; // int N = sizeof(Q) / sizeof(Q[0]); for ( int i = 0 ; i < 2 ; i++) { System.out.print((sum[Q[i][ 1 ]] - sum[Q[i][ 0 ] - 1 ]) + " " ); } } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to implement # the above approach MAX = 1001 # Function to find the smallest # prime factor of all the numbers # in range [0, MAX] def sieve(): # Stores smallest prime factor of all # the numbers in the range [0, MAX] global MAX spf = [ 0 ] * MAX # No smallest prime factor of # 0 and 1 exists spf[ 0 ] = spf[ 1 ] = - 1 # Traverse all the numbers # in the range [1, MAX] for i in range ( 2 , MAX ): # Update spf[i] spf[i] = i # Update all the numbers whose # smallest prime factor is 2 for i in range ( 4 , MAX , 2 ): spf[i] = 2 # Traverse all the numbers in # the range [1, sqrt(MAX)] for i in range ( 3 , MAX ): # Check if i is a prime number if (spf[i] = = i): # Update all the numbers whose # smallest prime factor is i for j in range (i * i, MAX ): # Check if j is # a prime number if (spf[j] = = j): spf[j] = i return spf # Function to find count of # prime factor of num def countFactors(spf, num): # Stores count of # prime factor of num count = 0 # Calculate count of # prime factor while (num > 1 ): # Update count count + = 1 # Update num num = num / / spf[num] return count # Function to precalculate the count of # numbers in the range [0, i] whose count # of prime factors is a prime number def precalculateSum(spf): # Stores the sum of all the numbers # in the range[0, i] count of # prime factor is a prime number sum = [ 0 ] * MAX # Traverse all the numbers in # the range [1, MAX] for i in range ( 1 , MAX ): # Stores count of prime factor of i prime_factor = countFactors(spf, i) # If count of prime factor is # a prime number if (spf[prime_factor] = = prime_factor): # Update sum[i] sum [i] = sum [i - 1 ] + 1 else : # Update sum[i] sum [i] = sum [i - 1 ] return sum # Driver code if __name__ = = '__main__' : # Stores smallest prime factor of all # the numbers in the range [0, MAX] spf = sieve() # Stores the sum of all the numbers # in the range[0, i] count of # prime factor is a prime number sum = precalculateSum(spf) Q = [ [ 4 , 8 ], [ 30 , 32 ] ] sum [Q[ 0 ][ 1 ]] + = 1 # N = sizeof(Q) / sizeof(Q[0]); for i in range ( 0 , 2 ): print (( sum [Q[i][ 1 ]] - sum [Q[i][ 0 ]]), end = " " ) # This code is contributed by Princi Singh |
C#
// C# program to implement // the above approach using System; class GFG{ public static int MAX = 1001; // Function to find the smallest // prime factor of all the numbers // in range [0, MAX] public static int [] sieve() { // Stores smallest prime factor // of all the numbers in the // range [0, MAX] int []spf = new int [MAX]; // No smallest prime factor // of 0 and 1 exists spf[0] = spf[1] = -1; // Traverse all the numbers // in the range [1, MAX] for ( int i = 2; i < MAX; i++) { // Update spf[i] spf[i] = i; } // Update all the numbers whose // smallest prime factor is 2 for ( int i = 4; i < MAX; i = i + 2) { spf[i] = 2; } // Traverse all the numbers in // the range [1, sqrt(MAX)] for ( int i = 3; i * i < MAX; i++) { // Check if i is a prime number if (spf[i] == i) { // Update all the numbers // whose smallest prime // factor is i for ( int j = i * i; j < MAX; j = j + i) { // Check if j is // a prime number if (spf[j] == j) { spf[j] = i; } } } } return spf; } // Function to find count of // prime factor of num public static int countFactors( int []spf, int num) { // Stores count of // prime factor of num int count = 0; // Calculate count of // prime factor while (num > 1) { // Update count count++; // Update num num = num / spf[num]; } return count; } // Function to precalculate the count of // numbers in the range [0, i] whose count // of prime factors is a prime number public static int [] precalculateSum( int []spf) { // Stores the sum of all the numbers // in the range[0, i] count of // prime factor is a prime number int []sum = new int [MAX]; // Update sum[0] sum[0] = 0; // Traverse all the numbers in // the range [1, MAX] for ( int i = 1; i < MAX; i++) { // Stores count of prime factor of i int prime_factor = countFactors(spf, i); // If count of prime factor is // a prime number if (spf[prime_factor] == prime_factor) { // Update sum[i] sum[i] = sum[i - 1] + 1; } else { // Update sum[i] sum[i] = sum[i - 1]; } } return sum; } // Driver code public static void Main(String[] args) { // Stores smallest prime factor // of all the numbers in the // range [0, MAX] int []spf = sieve(); // Stores the sum of all the // numbers in the range[0, i] // count of prime factor is a // prime number int []sum = precalculateSum(spf); int [,]Q = {{4, 8}, {30, 32}}; // int N = sizeof(Q) / sizeof(Q[0]); for ( int i = 0; i < 2; i++) { Console.Write((sum[Q[i, 1]] - sum[Q[i, 0] - 1]) + " " ); } } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach let MAX = 1001 // Function to find the smallest prime factor // of all the numbers in range [0, MAX] function sieve() { // Stores smallest prime factor of all // the numbers in the range [0, MAX] let spf = new Array(MAX); // No smallest prime factor of // 0 and 1 exists spf[0] = spf[1] = -1; // Traverse all the numbers // in the range [1, MAX] for (let i = 2; i < MAX; i++) { // Update spf[i] spf[i] = i; } // Update all the numbers whose // smallest prime factor is 2 for (let i = 4; i < MAX; i = i + 2) { spf[i] = 2; } // Traverse all the numbers in // the range [1, sqrt(MAX)] for (let i = 3; i * i < MAX; i++) { // Check if i is a prime number if (spf[i] == i) { // Update all the numbers whose // smallest prime factor is i for (let j = i * i; j < MAX; j = j + i) { // Check if j is // a prime number if (spf[j] == j) { spf[j] = i; } } } } return spf; } // Function to find count of // prime factor of num function countFactors(spf, num) { // Stores count of // prime factor of num let count = 0; // Calculate count of // prime factor while (num > 1) { // Update count count++; // Update num num = num / spf[num]; } return count; } // Function to precalculate the count of // numbers in the range [0, i] whose count // of prime factors is a prime number function precalculateSum(spf) { // Stores the sum of all the numbers // in the range[0, i] count of // prime factor is a prime number let sum = new Array(MAX); // Update sum[0] sum[0] = 0; // Traverse all the numbers in // the range [1, MAX] for (let i = 1; i < MAX; i++) { // Stores count of prime factor of i let prime_factor = countFactors(spf, i); // If count of prime factor is // a prime number if (spf[prime_factor] == prime_factor) { // Update sum[i] sum[i] = sum[i - 1] + 1; } else { // Update sum[i] sum[i] = sum[i - 1]; } } return sum; } // Driver Code // Stores smallest prime factor of all // the numbers in the range [0, MAX] let spf = sieve(); // Stores the sum of all the numbers // in the range[0, i] count of // prime factor is a prime number let sum = precalculateSum(spf); let Q = [ [ 4, 8 ], [ 30, 32 ] ]; // let N = sizeof(Q) / sizeof(Q[0]); for (let i = 0; i < 2; i++) { document.write((sum[Q[i][1]] - sum[Q[i][0] - 1]) + " " ); } // This code is contributed by gfgking </script> |
3 2
Time Complexity: O(|Q| + (MAX *log(log(MAX))))
Auxiliary Space: O(MAX)