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 1000000int prime[MAX + 1];// Function to update prime[]// such prime[i] stores the// count of prime numbers <= ivoid 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 codeint 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 approachimport 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 = 1000000prime = [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 approachusing 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 approachconst MAX = 1000000;let prime = new Array(MAX + 1);// Function to update prime[]// such prime[i] stores the// count of prime numbers <= ifunction 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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!