2
\$\begingroup\$
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--;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Can you fix the formatting of the code? \$\endgroup\$ – Bakuriu Sep 10 '13 at 11:17
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Jamal Sep 10 '13 at 12:27
  • \$\begingroup\$ 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 \$\endgroup\$ – rahul_raghavan Sep 10 '13 at 12:31
  • \$\begingroup\$ Right, and that algorithm should help. There's some pseudocode on the Wikipedia page, too. \$\endgroup\$ – Jamal Sep 10 '13 at 12:34
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ I did'nt get get it how can you optimize it to one loop \$\endgroup\$ – rahul_raghavan Sep 10 '13 at 13:36
-1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.