Count of non co | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1005 ; void preCalculate ( vector < int > & phi , vector < 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 ] ) ; } void countPairs ( int * arr , int N ) { vector < int > phi ( 1e5 , 0 ) ; vector < int > ans ( 1e5 , 0 ) ; preCalculate ( phi , ans ) ; for ( int i = 0 ; i < N ; ++ i ) { cout << ans [ arr [ i ] ] << " ▁ " ; } } int main ( ) { int arr [ ] = { 5 , 10 , 20 } ; int N = 3 ; countPairs ( arr , N ) ; }