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