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--;}
How can I optimize this code that finds the GCD?
java;optimization;algorithm;performance
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;}