Count pairs in an array whose product is composite number | Js program to implement the above approach ; Function to get all the prime numbers in the range [ 1 , X ] ; Stores the boolean value to check if a number is prime or not ; Mark all non prime numbers as false ; if p is a prime number ; Mark i as a composite number ; Function to get the count of pairs whose product is a composite number ; Stores the boolean value to check if a number is prime or not ; Stores the count of 1 s ; Stores the count of prime numbers ; Traverse the given array . ; Stores count of pairs whose product is not a composite number ; Stores the count of pairs whose product is composite number ; Driver Code
let X = 1000000 ; function getPrimeNum ( ) { let prime = [ ] ; for ( let i = 0 ; i < X ; i ++ ) { prime . push ( true ) ; } prime [ 0 ] = false ; prime [ 1 ] = false ; for ( let p = 2 ; p * p <= prime . length ; p ++ ) { if ( prime [ p ] ) { for ( let i = p * 2 ; i <= prime . length ; i += p ) prime [ i ] = false ; } } return prime ; } function cntPairs ( arr , N ) { let isPrime = getPrimeNum ( ) ; let cntOne = 0 ; let cntPrime = 0 ; for ( let i = 0 ; i < N ; i ++ ) { if ( arr [ i ] == 1 ) { cntOne += 1 ; } else if ( isPrime [ i ] ) { cntPrime += 1 ; } } let cntNonComp = 0 ; cntNonComp = cntPrime * cntOne + Math . floor ( cntOne * ( cntOne - 1 ) / 2 ) ; let res = 0 ; res = N * Math . floor ( ( N - 1 ) / 2 ) - cntNonComp ; return res ; } let arr = [ 1 , 1 , 2 , 2 , 8 ] ; let N = arr . length ; document . write ( cntPairs ( arr , N ) ) ;