Count smaller primes on the right of each array element | ''Python3 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
maxn = int ( 1e6 ) + 5 NEW_LINE BITree = [ 0 ] * ( maxn ) NEW_LINE def is_prime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT i = 2 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return True NEW_LINE DEDENT def update_bitree ( index , value ) : NEW_LINE INDENT while ( index <= maxn ) : NEW_LINE INDENT BITree [ index ] += value NEW_LINE index += ( index & ( - index ) ) NEW_LINE DEDENT DEDENT def sum_bitree ( index ) : NEW_LINE INDENT s = 0 NEW_LINE while ( index > 0 ) : NEW_LINE INDENT s += BITree [ index ] NEW_LINE index -= ( index & ( - index ) ) NEW_LINE DEDENT return s NEW_LINE DEDENT def countSmallerPrimes ( ar , N ) : NEW_LINE INDENT ans = [ 0 ] * ( N ) NEW_LINE global BITree NEW_LINE for i in range ( N - 1 , 0 , - 1 ) : NEW_LINE INDENT ans [ i ] = sum_bitree ( ar [ i ] ) NEW_LINE if ( is_prime ( ar [ i ] ) ) : NEW_LINE INDENT update_bitree ( ar [ i ] , 1 ) NEW_LINE DEDENT DEDENT ans [ 0 ] = 2 NEW_LINE for i in range ( N ) : NEW_LINE INDENT print ( ans [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT ar = [ 5 , 5 , 17 , 9 , 12 , 15 , 11 , 7 , 39 , 3 ] NEW_LINE N = len ( ar ) NEW_LINE countSmallerPrimes ( ar , N ) NEW_LINE DEDENT