Sum of all composite numbers lying in the range [ L , R ] for Q queries | Prefix array to precompute the sum of all composite number ; Function that return number num if num is composite else return 0 ; Corner cases ; This is checked so that we can skip middle five numbers in below loop ; Function to precompute the sum of all composite numbers upto 100000 ; checkcomposite ( ) return the number i if i is composite else return 0 ; Function to print the sum for each query ; Function to prsum of all composite numbers between ; Function that pre computes the sum of all composite numbers ; Iterate over all Queries to print the sum ; Driver code ; Queries ; Function that print the the sum of all composite number in Range [ L , R ]
pref = [ 0 ] * 100001 NEW_LINE def isComposite ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return n NEW_LINE DEDENT i = 5 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return n NEW_LINE DEDENT i = i + 6 NEW_LINE DEDENT return 0 NEW_LINE DEDENT def preCompute ( ) : NEW_LINE INDENT for i in range ( 1 , 100001 ) : NEW_LINE INDENT pref [ i ] = pref [ i - 1 ] + isComposite ( i ) NEW_LINE DEDENT DEDENT def printSum ( L , R ) : NEW_LINE INDENT print ( pref [ R ] - pref [ L - 1 ] ) NEW_LINE DEDENT def printSumcomposite ( arr , Q ) : NEW_LINE INDENT preCompute ( ) NEW_LINE for i in range ( Q ) : NEW_LINE INDENT printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT Q = 2 NEW_LINE arr = [ [ 10 , 13 ] , [ 12 , 21 ] ] NEW_LINE printSumcomposite ( arr , Q ) NEW_LINE DEDENT