Sum of all composite numbers lying in the range [ L , R ] for Q queries | C ++ implementation to find the sum of all composite numbers in the given range ; Prefix array to precompute the sum of all composite numbers ; 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 10 ^ 5 ; isComposite ( ) return the number i if i is Composite else return 0 ; Function to print the sum for each query ; Function to print sum of all Composite numbers between [ L , R ] ; 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 ]
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long pref [ 100001 ] ; int isComposite ( int n ) { if ( n <= 1 ) return 0 ; if ( n <= 3 ) return 0 ; if ( n % 2 == 0 n % 3 == 0 ) return n ; for ( int i = 5 ; i * i <= n ; i = i + 6 ) if ( n % i == 0 || n % ( i + 2 ) == 0 ) return n ; return 0 ; } void preCompute ( ) { for ( int i = 1 ; i <= 100000 ; ++ i ) { pref [ i ] = pref [ i - 1 ] + isComposite ( i ) ; } } void printSum ( int L , int R ) { cout << pref [ R ] - pref [ L - 1 ] << endl ; } void printSumComposite ( int arr [ ] [ 2 ] , int Q ) { preCompute ( ) ; for ( int i = 0 ; i < Q ; i ++ ) { printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ; } } int main ( ) { int Q = 2 ; int arr [ ] [ 2 ] = { { 10 , 13 } , { 12 , 21 } } ; printSumComposite ( arr , Q ) ; return 0 ; }