Count smaller primes on the right of each array element | Java Program for the above approach include " bits / stdJava . h " ; 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
import java . util . * ; class GFG { static int maxn = ( int ) 1e6 + 5 ; static int [ ] BITree = new int [ maxn ] ; static boolean is_prime ( int n ) { if ( n <= 1 ) return false ; for ( int i = 2 ; i * i <= n ; i ++ ) if ( n % i == 0 ) return false ; return true ; } static void update_bitree ( int BITree [ ] , int index , int value ) { while ( index <= maxn ) { BITree [ index ] += value ; index += ( index & ( - index ) ) ; } } static int sum_bitree ( int BITree [ ] , int index ) { int s = 0 ; while ( index > 0 ) { s += BITree [ index ] ; index -= ( index & ( - index ) ) ; } return s ; } static void countSmallerPrimes ( int BITree [ ] , int ar [ ] , int N ) { int [ ] ans = new int [ 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 ++ ) System . out . print ( ans [ i ] + " ▁ " ) ; } public static void main ( String [ ] args ) { int ar [ ] = { 5 , 5 , 17 , 9 , 12 , 15 , 11 , 7 , 39 , 3 } ; int N = ar . length ; countSmallerPrimes ( BITree , ar , N ) ; } }