How can I optimize this code that finds the GCD?

Question

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--;
}

• Bakuriu: Can you fix the formatting of the code?
• Jamal: 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).
• rahul_raghavan: 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
• Jamal: Right, and that algorithm should help. There's some pseudocode on the Wikipedia page, too.

Answer 1

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;
}

• rahul_raghavan: I did'nt get get it how can you optimize it to one loop

Answer 2

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.