How can I optimize this code that finds the GCD?
Assuming that findgcd is correctly implemented and that i and j are guaranteed to both be non-negative, findgcd(i, j) == j is equivalent to j != 0 &amp;&amp; i % j == 0. That allows a further optimisation to a single loop, because the number of values in 1..n which are divisible by j is floor(n/j):

for (int j = 1; j &lt;= n; j++)
{
    count += n;
    gcdCount += n / j;
}