# Error in calculating GCD and LCM

I have written the below code to calculate the GCD and LCM.

It works fine for the given set of inputs in the question as well as for some other inputs which i tried.

If when running on codechef it says Wrong Answer.

Not sure what is causing this error.

``````import java.io.BufferedReader;
``````

import java.io.PrintWriter;
import java.util.StringTokenizer;

public class GCDandLCM
{

``````public static void main(String[] args) throws Exception
{

PrintWriter pw = new PrintWriter(System.out);

int gcd = 0;

while(testcases-- > 0)
{

int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());

for (int i = 1; i <= a; i++)
{
if(a % i == 0 && b % i == 0)
gcd = i;
}

pw.println(gcd + " " + a * b / gcd);
}

pw.flush();

}
``````

}

Dont print superfluous print statements like â€śGcd=â€ť+gcd etc. It causes WA. Print EXACTLY whats asked in the output section.

Your algorithm looks correct. Since you have not given the link of the problem you are referring to, I would suggest that you should check the constraints given in the problem statement. Since you have used int, it can store values up to approximately 10^9.

Also, your algorithm is inefficient as it checks the divisibility for every number. You can use Euclidâ€™s algorithm to make it run faster.

A recursive implementation is as follows :

``````int gcd(int a , int b)
{
if(a % b == 0)
return b;
return gcd(b , a % b);
}``````
1 Like

pw.println(gcd + " " + a * b / gcd);

The above statement is only printing GCD and LCM with a " " between them as asked in the question.

please correct if it is wrong interpretation of the output

1 Like

Please post the question link. You got back after too long time- I lost track of the question.