Count of non co | C ++ program for the above approach ; Recursive function to return gcd of two numbers ; Function to count the number of non co - prime pairs for each query ; Traverse the array arr [ ] ; Stores the count of non co - prime pairs ; Iterate over the range [ 1 , x ] ; Iterate over the range [ x , y ] ; If gcd of current pair is greater than 1 ; Driver Code ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } void countPairs ( int * arr , int N ) { for ( int i = 0 ; i < N ; i ++ ) { int count = 0 ; for ( int x = 1 ; x <= arr [ i ] ; x ++ ) { for ( int y = x ; y <= arr [ i ] ; y ++ ) { if ( gcd ( x , y ) > 1 ) count ++ ; } } cout << count << " ▁ " ; } } int main ( ) { int arr [ ] = { 5 , 10 , 20 } ; int N = 3 ; countPairs ( arr , N ) ; return 0 ; }