Remove all triplets which have gcd equal to a multiple of i
for ( int i = 1000000 ; i >= 1 ; i -- ) { for ( int j = 2 * i ; j <= 1000000 ; j += i ) { cnt [ i ] -= cnt [ j ] ; } } cout << " Number ▁ of ▁ triplets ▁ " << " with ▁ GCD ▁ " << K ; cout << " ▁ are ▁ " << cnt [ K ] ; }