Queries for the difference between the count of composite and prime numbers in a given range | C ++ implementation of the approach ; Function to update prime [ ] such prime [ i ] stores the count of prime numbers <= i ; Initialization ; 0 and 1 are not primes ; Mark composite numbers as false and prime numbers as true ; Update prime [ ] such that prime [ i ] will store the count of all the prime numbers <= i ; Function to return the absolute difference between the number of primes and the number of composite numbers in the range [ l , r ] ; Total elements in the range ; Count of primes in the range [ l , r ] ; Count of composite numbers in the range [ l , r ] ; Return the sbsolute difference ; Driver code ; Perform queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000000 NEW_LINE int prime [ MAX + 1 ] ; void updatePrimes ( ) { for ( int i = 2 ; i <= MAX ; i ++ ) { prime [ i ] = 1 ; } prime [ 0 ] = prime [ 1 ] = 0 ; for ( int i = 2 ; i * i <= MAX ; i ++ ) { if ( prime [ i ] == 1 ) { for ( int j = i * i ; j <= MAX ; j += i ) { prime [ j ] = 0 ; } } } for ( int i = 1 ; i <= MAX ; i ++ ) { prime [ i ] += prime [ i - 1 ] ; } } int getDifference ( int l , int r ) { int total = r - l + 1 ; int primes = prime [ r ] - prime [ l - 1 ] ; int composites = total - primes ; return ( abs ( primes - composites ) ) ; } int main ( ) { int queries [ ] [ 2 ] = { { 1 , 10 } , { 5 , 30 } } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; updatePrimes ( ) ; for ( int i = 0 ; i < q ; i ++ ) cout << getDifference ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) << endl ; return 0 ; }