Thread: solving efficiently

i need to solve this equation efficiently

m+n-gcd(m,n)=N

i.e, when N is given i need to find NUMBER OF PAIRS of m,n that satisify the equation ( also for ex: 45,100 is same as 100,45 )

here is what i do

Code:

	lim=N/2;

	for(i=2;i<=lim;i++)

	{

		for(j=N-i+1;j<=N;j++)

			if(i+j-gcd(i,j)==N)
	count++;

	}

	printf("%d",count+2);

N<10^6

can any 1 help !!!