Computing count of prime numbers using sieve
for ( int i = 2 ; i <= sqrt ( n ) ; i ++ ) { if ( prime [ i ] ) for ( int factor = 2 ; factor * i <= n ; factor ++ ) prime [ factor * i ] = false ; } int primeIndices = 0 ; for ( int i = 1 ; i <= n ; i ++ ) if ( prime [ i ] ) primeIndices ++ ; int mod = 1e9 + 7 , res = 1 ;