Why in some cases my program gives the wrong result?

Question

I performed an implementation of the Euclidean algorithm in Java to find the Greatest Common Divisor (GCD) of two given numbers.

For the most part, my program works fine, I checked it with several random sets of numbers, although I found in one case (that I know) that it gives the wrong output, which for the following combination of numbers:

Enter the integer a: 8965 Enter the integer b: 55

The output of the program should be 55, although this is not so. The following is displayed:

gcd = 1 Lead time: 0.005747ms.

I'm not sure why this particular combination of numbers causes a problem, since it works great for other numbers, for example, here are the results for another set of numbers:

Enter an integer a: 15000

Enter the integer b: 5325

gcd = 75

Lead time: 0.007389ms.

import java.util.Scanner; public class EuclideanAlgorithm { public static void main (String [] args) { int a, b; try(Scanner sc = new Scanner(System.in);) { System.out.print("Enter integer a: "); a = sc.nextInt(); System.out.print("Enter integer b: "); b = sc.nextInt(); } long start = System.nanoTime(); int answer = EuclideanAlgorithm(a, b); long stop = System.nanoTime(); System.out.println("gcd = " + answer); System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms."); } public EuclideanAlgorithm() {}; //Suppress default constructor private static int EuclideanAlgorithm(int a, int b) { if ( (a == 0) || (b == 0)) { return 0; } if (b > a) { int temp = a; a = b; b = temp; } int gcd = 1; while(gcd != 0) { if( (a % b) == 0) { break; } gcd = a % b; a = b; b = gcd; } return gcd; } } 

Answer 1

Whenever one of your numbers a , b is a multiple of the other, then your if condition will return break and 1 , which is not true. But the rest of the algorithm is also incorrect.

According to the pseudo-code for the Euclidean algorithm :

 function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a 

You need to check not b not 0 , not gcd. You will need to change your code in accordance with this algorithm; Your code currently does not match this algorithm.

Answer 2

Due to if condition inside this while loop

 int gcd = 1; while(gcd != 0) { if( (a % b) == 0) { break; } gcd = a % b; a = b; b = gcd; } 

So, in the case when a% b = 0 at the beginning → the result is always 1.

You need to handle this case separately.

 int gcd = b; while(a % b != 0){ gcd = a % b; a = b; b = gcd; } 

Answer 3

Easy 55 divides 8965, which means the program is interrupted on the first line and returns an initial value of 1.

Instead, something like this might help.

 int gcd = 1; if( (a % b) == 0) { return b; } while(gcd != 0) { if( (a % b) == 0) { break; } gcd = a % b; a = b; b = gcd; }