Count of non co | Java program for the above approach ; Auxiliary function to pre - compute the answer for each array ; Iterate over the range [ 1 , MAX ] ; Iterate over the range [ 1 , MAX ] ; If the number is prime ; Subtract the number of pairs which has i as one of their factors ; Iterate over the range [ 1 , MAX ] ; Function to count the number of non co - prime pairs for each query ; The i - th element stores the count of element that are co - prime with i ; Stores the resulting array ; Function Call ; Traverse the array arr [ ] ; Driver Code ; Given Input ; Function Call
import java . util . * ; class GFG { static int MAX = 1005 ; static void preCalculate ( int [ ] phi , int [ ] ans ) { phi [ 0 ] = 0 ; phi [ 1 ] = 1 ; for ( int i = 2 ; i <= MAX ; i ++ ) phi [ i ] = i ; for ( int i = 2 ; i <= MAX ; i ++ ) { if ( phi [ i ] == i ) { for ( int j = i ; j <= MAX ; j += i ) phi [ j ] -= ( phi [ j ] / i ) ; } } for ( int i = 1 ; i <= MAX ; i ++ ) ans [ i ] = ans [ i - 1 ] + ( i - phi [ i ] ) ; } static void countPairs ( int [ ] arr , int N ) { int [ ] phi = new int [ 100000 ] ; Arrays . fill ( phi , 0 ) ; int [ ] ans = new int [ 100000 ] ; Arrays . fill ( ans , 0 ) ; preCalculate ( phi , ans ) ; for ( int i = 0 ; i < N ; ++ i ) { System . out . print ( ans [ arr [ i ] ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 5 , 10 , 20 } ; int N = 3 ; countPairs ( arr , N ) ; } }