CODEWITHSUNDEEP
javaalgorithmgreatest-common-divisor
foodnliquor
foodnliquor

Reputation: 13

Infinite loop in implementation of Euclid's greatest common denominator method

Logical Error with the second println statement causes an infinite loop in my code below.

It's inside the while loop which I understand causes it to keep printing because the while test is true. Using 48 and 18 as num1 and num2 respectively, I get the correct answer of the GCD being 6. The placement of the print out statement is wrong, and I cannot figure out where to put it.

My code finds the GCD of two integers as long as either are not negative. I used Euclid's method.

Thanks for any help!

import java.util.*;

public class Chapter5Lab_Problem1 {


  public static void main(String[] args) { 
    Scanner console = new Scanner(System.in);
    System.out.print("Type the first integer to find GCD");
    int num1 = console.nextInt();
    System.out.print("Type the second integer to find GCD ");
    int num2 = console.nextInt();
    gcd(num1,num2);
  }

  public static void gcd( int x, int y){
    while( x >= 0 && y >= 0){
      if( x == 0){
        System.out.println("The GCD is " + y);
      }
      while( y != 0){
        if( x > y){
          x = x - y;
        }else{
          y = y - x;
        }

      }
     System.out.println("The GCF is " + x); 
    } 
  } 
}

Upvotes: 0

Views: 552

Answers (2)

Zechariah Hutchins
Zechariah Hutchins

Reputation: 31

This is a recursive answer. Teachers love recursion. Recursion is risky when it is infinite or too long of a stack for the program to hold.

public static int GCD(int n1, int n2){

  if(a==0 || b==0)
    return a+b;

  return GCD(n2, n1%n2)
}

If you must do a loop, here is that implementation

int n3;
while(n != 0 || n2!= 0){

  n3 = n2;
  n2 = n1%n2;
  n1 = n3;
}

return n1+n2;

Upvotes: 1

Sinkingpoint
Sinkingpoint

Reputation: 7634

X and Y will always be >= 0. The minimum they can become in this algorithm is 0, thus the condition for the first while statement always holds. Try x > 0 && y > 0 instead.

Upvotes: 1

Related Questions