Finding a irreducible fraction

Question

Given a positive integer n, it is asked to find the probability that one can pick two numbersA and B from the set [1...n], such that the GCD of A and B is B. So my approach was to calculate number of pairs such that one is divisible by another. And the answer was expected to be in irreducible fraction form.
EXAMPLE:
1 2 3
OUTPUT:
1/1 3/4 5/9

long n = sc.nextLong();
long sum=0;
for(long i=1;i<=n/2;i++)
    sum+=(n/i)-1;
 long tot = n*n;
 sum+=n;
 long bro = hcf(tot,sum);
 sum/=bro;
 tot/=bro;
 System.out.print(sum+"/"+tot);

And my hcf function was:

public static long hcf(long n1,long n2)
{
    if (n2!=0)
        return hcf(n2, n1%n2);
    else 
        return n1;
}

But the compiler message was time-out. I think there may be some problem with the hcf function or there is a better and efficient method for finding the irreducible fraction. Since it was successful for smaller inputs, I think there is most probably an efficient method for finding the irreducible fraction form. Any suggestions?

Answer 1

Your hcf function is not too slow. Instead, the problem is that you have a for loop which iterates O(n) times, which is quite a lot when n = 10^9. You can get it down to O(sqrt(n)) by only counting cases where B <= sqrt(A). That will give you about half of the cases, because usually exactly one of B and A/B is smaller than sqrt(A). The only exception is you have to account for cases when B * B = A.