Queries for the difference between the count of composite and prime numbers in a given range
Given Q queries where each query consists of two positive integers L and R and the task is to find the absolute difference between the count of prime numbers and the count of composite numbers in the range [L, R]
Examples:
Input: queries[][] = {{1, 10}}
Output:
2
2, 3, 5 and 7 are the only primes in the given range.
So, rest of the 6 integers are composite.
|6 – 4| = 2Input: queries[][] = {{4, 10}, {5, 30}}
Output:
3
10
Approach:
- Using Sieve of Eratosthenes, generate an array prime[i] such that prime[i] = 1 if i is prime else 0.
- Now update the prime[] array such that prime[i] stores the count of prime numbers which are ? i.
- For every query, the count of prime numbers in the range [L, R] can be found by prime[R] – prime[L – 1], and the count of composite numbers will be the count of prime numbers subtracted from the total elements.
- Print the absolute difference between the count of primes and the count of composites found in the previous step.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define MAX 1000000 int prime[MAX + 1]; // Function to update prime[] // such prime[i] stores the // count of prime numbers <= i void updatePrimes() { // prime[] marks all prime numbers as true // so prime[i] = 1 if ith number is a prime // Initialization for ( int i = 2; i <= MAX; i++) { prime[i] = 1; } // 0 and 1 are not primes prime[0] = prime[1] = 0; // Mark composite numbers as false // and prime numbers as true for ( int i = 2; i * i <= MAX; i++) { if (prime[i] == 1) { for ( int j = i * i; j <= MAX; j += i) { prime[j] = 0; } } } // Update prime[] such that // prime[i] will store the count of // all the prime numbers <= i for ( int i = 1; i <= MAX; i++) { prime[i] += prime[i - 1]; } } // Function to return the absolute difference // between the number of primes and the number // of composite numbers in the range [l, r] int getDifference( int l, int r) { // Total elements in the range int total = r - l + 1; // Count of primes in the range [l, r] int primes = prime[r] - prime[l - 1]; // Count of composite numbers // in the range [l, r] int composites = total - primes; // Return the absolute difference return ( abs (primes - composites)); } // Driver code int main() { int queries[][2] = { { 1, 10 }, { 5, 30 } }; int q = sizeof (queries) / sizeof (queries[0]); updatePrimes(); // Perform queries for ( int i = 0; i < q; i++) cout << getDifference(queries[i][0], queries[i][1]) << endl; return 0; } |
Java
// Java implementation of the approach import java.io.*; class GFG { static int MAX = 1000000 ; static int []prime = new int [MAX + 1 ]; // Function to update prime[] // such prime[i] stores the // count of prime numbers <= i static void updatePrimes() { // prime[] marks all prime numbers as true // so prime[i] = 1 if ith number is a prime // Initialization for ( int i = 2 ; i <= MAX; i++) { prime[i] = 1 ; } // 0 and 1 are not primes prime[ 0 ] = prime[ 1 ] = 0 ; // Mark composite numbers as false // and prime numbers as true for ( int i = 2 ; i * i <= MAX; i++) { if (prime[i] == 1 ) { for ( int j = i * i; j <= MAX; j += i) { prime[j] = 0 ; } } } // Update prime[] such that // prime[i] will store the count of // all the prime numbers <= i for ( int i = 1 ; i <= MAX; i++) { prime[i] += prime[i - 1 ]; } } // Function to return the absolute difference // between the number of primes and the number // of composite numbers in the range [l, r] static int getDifference( int l, int r) { // Total elements in the range int total = r - l + 1 ; // Count of primes in the range [l, r] int primes = prime[r] - prime[l - 1 ]; // Count of composite numbers // in the range [l, r] int composites = total - primes; // Return the absolute difference return (Math.abs(primes - composites)); } // Driver code public static void main (String[] args) { int queries[][] = { { 1 , 10 }, { 5 , 30 } }; int q = queries.length; updatePrimes(); // Perform queries for ( int i = 0 ; i < q; i++) System.out.println (getDifference(queries[i][ 0 ], queries[i][ 1 ])); } } // This code is contributed by jit_t |
Python3
# Python3 implementation of the approach from math import sqrt MAX = 1000000 prime = [ 0 ] * ( MAX + 1 ); # Function to update prime[] # such prime[i] stores the # count of prime numbers <= i def updatePrimes() : # prime[] marks all prime numbers as true # so prime[i] = 1 if ith number is a prime # Initialization for i in range ( 2 , MAX + 1 ) : prime[i] = 1 ; # 0 and 1 are not primes prime[ 0 ] = prime[ 1 ] = 0 ; # Mark composite numbers as false # and prime numbers as true for i in range ( 2 , int (sqrt( MAX ) + 1 )) : if (prime[i] = = 1 ) : for j in range (i * i, MAX , i) : prime[j] = 0 ; # Update prime[] such that # prime[i] will store the count of # all the prime numbers <= i for i in range ( 1 , MAX ) : prime[i] + = prime[i - 1 ]; # Function to return the absolute difference # between the number of primes and the number # of composite numbers in the range [l, r] def getDifference(l, r) : # Total elements in the range total = r - l + 1 ; # Count of primes in the range [l, r] primes = prime[r] - prime[l - 1 ]; # Count of composite numbers # in the range [l, r] composites = total - primes; # Return the absolute difference return ( abs (primes - composites)); # Driver code if __name__ = = "__main__" : queries = [ [ 1 , 10 ],[ 5 , 30 ] ]; q = len (queries); updatePrimes(); # Perform queries for i in range (q) : print (getDifference(queries[i][ 0 ], queries[i][ 1 ])) # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 1000000; static int []prime = new int [MAX + 1]; // Function to update prime[] // such prime[i] stores the // count of prime numbers <= i static void updatePrimes() { // prime[] marks all prime numbers as true // so prime[i] = 1 if ith number is a prime // Initialization for ( int i = 2; i <= MAX; i++) { prime[i] = 1; } // 0 and 1 are not primes prime[0] = prime[1] = 0; // Mark composite numbers as false // and prime numbers as true for ( int i = 2; i * i <= MAX; i++) { if (prime[i] == 1) { for ( int j = i * i; j <= MAX; j += i) { prime[j] = 0; } } } // Update prime[] such that // prime[i] will store the count of // all the prime numbers <= i for ( int i = 1; i <= MAX; i++) { prime[i] += prime[i - 1]; } } // Function to return the absolute difference // between the number of primes and the number // of composite numbers in the range [l, r] static int getDifference( int l, int r) { // Total elements in the range int total = r - l + 1; // Count of primes in the range [l, r] int primes = prime[r] - prime[l - 1]; // Count of composite numbers // in the range [l, r] int composites = total - primes; // Return the absolute difference return (Math.Abs(primes - composites)); } // Driver code public static void Main () { int [,]queries = { { 1, 10 }, { 5, 30 } }; int q = queries.GetLength(0); updatePrimes(); // Perform queries for ( int i = 0; i < q; i++) Console.WriteLine(getDifference(queries[i,0], queries[i,1])); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript implementation of the approach const MAX = 1000000; let prime = new Array(MAX + 1); // Function to update prime[] // such prime[i] stores the // count of prime numbers <= i function updatePrimes() { // prime[] marks all prime numbers as true // so prime[i] = 1 if ith number is a prime // Initialization for (let i = 2; i <= MAX; i++) { prime[i] = 1; } // 0 and 1 are not primes prime[0] = prime[1] = 0; // Mark composite numbers as false // and prime numbers as true for (let i = 2; i * i <= MAX; i++) { if (prime[i] == 1) { for (let j = i * i; j <= MAX; j += i) { prime[j] = 0; } } } // Update prime[] such that // prime[i] will store the count of // all the prime numbers <= i for (let i = 1; i <= MAX; i++) { prime[i] += prime[i - 1]; } } // Function to return the absolute difference // between the number of primes and the number // of composite numbers in the range [l, r] function getDifference(l, r) { // Total elements in the range let total = r - l + 1; // Count of primes in the range [l, r] let primes = prime[r] - prime[l - 1]; // Count of composite numbers // in the range [l, r] let composites = total - primes; // Return the absolute difference return (Math.abs(primes - composites)); } // Driver code let queries = [ [ 1, 10 ], [ 5, 30 ] ]; let q = queries.length; updatePrimes(); // Perform queries for (let i = 0; i < q; i++) document.write(getDifference(queries[i][0], queries[i][1]) + "<br>" ); </script> |
Output:
2 10
Time Complexity: O(q+MAX*log(log(MAX))) where q is number of queries and MAX=1000000
Auxiliary Space: O(MAX)