Queries for the difference between the count of composite and prime numbers in a given range | Javascript 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
const MAX = 1000000 ; let prime = new Array ( MAX + 1 ) ; function updatePrimes ( ) { for ( let i = 2 ; i <= MAX ; i ++ ) { prime [ i ] = 1 ; } prime [ 0 ] = prime [ 1 ] = 0 ; for ( let i = 2 ; i * i <= MAX ; i ++ ) { if ( prime [ i ] == 1 ) { for ( let j = i * i ; j <= MAX ; j += i ) { prime [ j ] = 0 ; } } } for ( let i = 1 ; i <= MAX ; i ++ ) { prime [ i ] += prime [ i - 1 ] ; } } function getDifference ( l , r ) { let total = r - l + 1 ; let primes = prime [ r ] - prime [ l - 1 ] ; let composites = total - primes ; return ( Math . abs ( primes - composites ) ) ; } let queries = [ [ 1 , 10 ] , [ 5 , 30 ] ] ; let q = queries . length ; updatePrimes ( ) ; for ( let i = 0 ; i < q ; i ++ ) document . write ( getDifference ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) + " " ) ;