Count smaller primes on the right of each array element | Javascript 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
let maxn = 1e6 + 5 ; let BITree = new Array ( maxn ) ; BITree . fill ( 0 ) ; function is_prime ( n ) { if ( n <= 1 ) return false ; for ( let i = 2 ; i * i <= n ; i ++ ) if ( n % i == 0 ) return false ; return true ; } function update_bitree ( BITree , index , value ) { while ( index <= maxn ) { BITree [ index ] += value ; index += ( index & ( - index ) ) ; } } function sum_bitree ( BITree , index ) { let s = 0 ; while ( index > 0 ) { s += BITree [ index ] ; index -= ( index & ( - index ) ) ; } return s ; } function countSmallerPrimes ( BITree , ar , N ) { let ans = new Array ( N ) ; for ( let 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 ( let i = 0 ; i < N ; i ++ ) document . write ( ans [ i ] + " " ) ; } let ar = [ 5 , 5 , 17 , 9 , 12 , 15 , 11 , 7 , 39 , 3 ] ; let N = ar . length ; countSmallerPrimes ( BITree , ar , N ) ;