Count pairs in an array whose product is composite number | Java 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 i is prime number ; Mark j 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
import java . util . * ; class GFG { public static int X = 1000000 ; public static boolean [ ] getPrimeNum ( ) { boolean isPrime [ ] = new boolean [ X ] ; Arrays . fill ( isPrime , true ) ; isPrime [ 0 ] = false ; isPrime [ 1 ] = false ; for ( int i = 2 ; i * i <= X ; i ++ ) { if ( isPrime [ i ] == true ) { for ( int j = i * i ; j < X ; j += i ) { isPrime [ j ] = false ; } } } return isPrime ; } public static int cntPairs ( int arr [ ] , int N ) { boolean isPrime [ ] = getPrimeNum ( ) ; int cntOne = 0 ; int cntPrime = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] == 1 ) { cntOne += 1 ; } else if ( isPrime [ i ] ) { cntPrime += 1 ; } } int cntNonComp = 0 ; cntNonComp = cntPrime * cntOne + cntOne * ( cntOne - 1 ) / 2 ; int res = 0 ; res = N * ( N - 1 ) / 2 - cntNonComp ; return res ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 1 , 2 , 2 , 8 } ; int N = arr . length ; System . out . println ( cntPairs ( arr , N ) ) ; } }