# How can I optimize this code that finds the GCD?

int count;
int gcdCount;
int testCase = 5;

while (testCase > 0)
{
int n = 5;
count = 0;
gcdCount = 0;
// to get two  random numbers a and b a<=n and b<=n
//get probablity of gcd(a,b) ==b
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
count++;
// check if gcd(i,j) is equal to second number j
if (findgcd(i, j) == j)
{
gcdCount++;
}
}
}
//return probability of gcdcount
System.out.println(gcdCount + "/" + count);
testCase--;
}

• Can you fix the formatting of the code? – Bakuriu Sep 10 '13 at 11:17
• I'd recommend the Euclidean algorithm for solving this problem as it's more efficient and probably clearer. You're using nested for-loops, giving you an easy O(n^2) (not a good thing). – Jamal Sep 10 '13 at 12:27
• Yes i wanted to optimize the inner for loop as it takes O(n^2) time the gcd part is not a problem i have calculated the gcd using Euclidean Algorithm in findgcd method – rahul_raghavan Sep 10 '13 at 12:31
• Right, and that algorithm should help. There's some pseudocode on the Wikipedia page, too. – Jamal Sep 10 '13 at 12:34

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 && 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 <= n; j++)
{
count += n;
gcdCount += n / j;
}

• I did'nt get get it how can you optimize it to one loop – rahul_raghavan Sep 10 '13 at 13:36

You do not need to increment "count" variable in every loop. The value of it depends on "n".

Here you can find some ways to optimize a loop: http://en.wikipedia.org/wiki/Loop_optimization

What is the difference between the test cases? For me it seems nothing change; you always run the same double for-loop.