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--;
}
\$\begingroup\$
\$\endgroup\$
4
-
1\$\begingroup\$ Can you fix the formatting of the code? \$\endgroup\$– BakuriuSep 10, 2013 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\$– JamalSep 10, 2013 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_raghavanSep 10, 2013 at 12:31
-
\$\begingroup\$ Right, and that algorithm should help. There's some pseudocode on the Wikipedia page, too. \$\endgroup\$– JamalSep 10, 2013 at 12:34
Add a comment
|
2 Answers
\$\begingroup\$
\$\endgroup\$
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;
}
answered Sep 10, 2013 at 12:58
-
\$\begingroup\$ I did'nt get get it how can you optimize it to one loop \$\endgroup\$ Sep 10, 2013 at 13:36
\$\begingroup\$
\$\endgroup\$
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.
