Count smaller primes on the right of each array element | C ++ Program for the above approach ; Function to check if a number is prime or not ; Function to update a Binary Tree ; Function to find the sum of all the elements which are less than or equal to index ; Function to find the number of smaller primes on the right for every array element ; Iterate the array in backwards ; Calculating the required number of primes ; If current array element is prime ; Update the Fenwick tree ; Driver Code ; Function call
#include " bits / stdc + + . h " NEW_LINE using namespace std ; const int maxn = 1e6 + 5 ; int BITree [ maxn ] ; bool is_prime ( int n ) { if ( n <= 1 ) return 0 ; for ( int i = 2 ; i * i <= n ; i ++ ) if ( n % i == 0 ) return 0 ; return 1 ; } void update_bitree ( int BITree [ ] , int index , int value ) { while ( index <= maxn ) { BITree [ index ] += value ; index += ( index & ( - index ) ) ; } } int sum_bitree ( int BITree [ ] , int index ) { int s = 0 ; while ( index > 0 ) { s += BITree [ index ] ; index -= ( index & ( - index ) ) ; } return s ; } void countSmallerPrimes ( int BITree [ ] , int ar [ ] , int N ) { int ans [ N ] ; for ( int i = N - 1 ; i >= 0 ; i -- ) { ans [ i ] = sum_bitree ( BITree , ar [ i ] ) ; if ( is_prime ( ar [ i ] ) ) update_bitree ( BITree , ar [ i ] , 1 ) ; } for ( int i = 0 ; i < N ; i ++ ) cout << ans [ i ] << " ▁ " ; } int main ( ) { int ar [ ] = { 5 , 5 , 17 , 9 , 12 , 15 , 11 , 7 , 39 , 3 } ; int N = sizeof ar / sizeof ar [ 0 ] ; countSmallerPrimes ( BITree , ar , N ) ; return 0 ; }