Queries for the difference between the count of composite and prime numbers in a given range | Python3 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
from math import sqrt NEW_LINE MAX = 1000000 NEW_LINE prime = [ 0 ] * ( MAX + 1 ) ; NEW_LINE def updatePrimes ( ) : NEW_LINE INDENT for i in range ( 2 , MAX + 1 ) : NEW_LINE INDENT prime [ i ] = 1 ; NEW_LINE DEDENT prime [ 0 ] = prime [ 1 ] = 0 ; NEW_LINE for i in range ( 2 , int ( sqrt ( MAX ) + 1 ) ) : NEW_LINE INDENT if ( prime [ i ] == 1 ) : NEW_LINE INDENT for j in range ( i * i , MAX , i ) : NEW_LINE INDENT prime [ j ] = 0 ; NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , MAX ) : NEW_LINE INDENT prime [ i ] += prime [ i - 1 ] ; NEW_LINE DEDENT DEDENT def getDifference ( l , r ) : NEW_LINE INDENT total = r - l + 1 ; NEW_LINE primes = prime [ r ] - prime [ l - 1 ] ; NEW_LINE composites = total - primes ; NEW_LINE return ( abs ( primes - composites ) ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT queries = [ [ 1 , 10 ] , [ 5 , 30 ] ] ; NEW_LINE q = len ( queries ) ; NEW_LINE updatePrimes ( ) ; NEW_LINE for i in range ( q ) : NEW_LINE INDENT print ( getDifference ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) ) NEW_LINE DEDENT DEDENT