How to write a simple Java program that finds the greatest common divisor between two numbers? [duplicate]

Question

Here is the question:

"Write a method named gcd that accepts two integers as parameters and returns the greatest common divisor of the two numbers. The greatest common divisor (GCD) of two integers a and b is the largest integer that is a factor of both a and b. The GCD of any number and 1 is 1, and the GCD of any number and 0 is that number.

One efficient way to compute the GCD of two numbers is to use Euclid's algorithm, which states the following:

GCD(A, B) = GCD(B, A % B) 
GCD(A, 0) = Absolute value of A"

I'm really confused as to how to solve this problem. I just want some hints and tips as to what I did wrong in the program I have so far. (I have to put in a Scanner, that is my teacher's requirement.) Don't give me a full code as I kinda want to solve this out myself. Maybe just give me a hint on how I incorporate this formula that you see above. (And if you're wondering why I put in the == 0, it's because I thought that if you have two numbers, say 0 and 90, their GCD would be 0 right??)

Also, my code has to include while loops...I would've preferred if loops...

Thanks in advance! :)

My current program:

public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        int a = console.nextInt();
        int b = console.nextInt();
        gcd (a, b);
    }

    public static void gcd(int a, int b) {
        System.out.print("Type in two numbers and I will print outs its Greatest Common Divisor: ");
        int gcdNum1 = console.nextInt();
        int gcdNum2 = console.nextInt();
        while (gcdNum1 == 0) {
            gcdNum1 = 0;
        }
        while (gcdNum2 > gcdNum1) {
            int gcd = gcdNum1 % gcdNum2;
        }
        System.out.print(gcdNum1 + gcdNum2);
    }
}

Fransis

Hint - you need a recursive call. – Pasticcio

You are passing a and b to your method as paramters, so there is no need to read them again from console (and console variable is not visible in the method, so your code won't compile anyway). Also, the first loop looks pretty infinite, if entered. – Sobersided

I would've preferred if loops... That's quite complicated since if is no loop – Hufnagel

Whoops, you're right. Haha typo. – Fransis

Answer 1

A recursive method would be:

static int gcd(int a, int b)
{
  if(a == 0 || b == 0) return a+b; // base case
  return gcd(b,a%b);
}

Using a while loop:

static int gcd(int a, int b)
{
  while(a!=0 && b!=0) // until either one of them is 0
  {
     int c = b;
     b = a%b;
     a = c;
  }
  return a+b; // either one is 0, so return the non-zero value
}

When I'm returning a+b, I'm actually returning the non-zero number assuming one of them is 0.

Befoul

I think your code assumes a > b, if someone calls gcd(2, 20), it won't work. – Articulation

@Articulation It would. In the next step, it would call gcd(20,2) – Befoul

Answer 2

You can also do it in a three line method:

public static int gcd(int x, int y){
  return (y == 0) ? x : gcd(y, x % y);
}

Here, if y = 0, x is returned. Otherwise, the gcd method is called again, with different parameter values.

Rabb

Answer 3

public static int GCD(int x, int y) {   
    int r;
    while (y!=0) {
        r = x%y;
        x = y;
        y = r;
    }
    return x;
}

Midweek

Answer 4

import java.util.Scanner;


public class Main {




public static void  main(String [] args)
{
    Scanner input = new Scanner(System.in);
    System.out.println("Please enter the first integer:");
    int b = input.nextInt();
    System.out.println("Please enter the second integer:");
    int d = input.nextInt();

    System.out.println("The GCD of " + b + " and " + d + " is " +  getGcd(b,d) + ".");
}


public static int getGcd(int b, int d)
{
    int gcd = 1;

    if(b>d)
    {
        for(int i = d; i >=1; i--)
        {
            if(b%i==0 && d%i ==0)
            {
                return i;
            }
        }
    }
    else
    {
        for(int j = b; j >=1; j--)
        {
            if(b%j==0 && d% j==0)
            {
                return j;
            }
        }
    }   
    return gcd;

}
}

Eugeniusz

Answer 5

One way to do it is the code below:

        int gcd = 0;
        while (gcdNum2 !=0 && gcdNum1 != 0 ) {
        if(gcdNum1 % gcdNum2 == 0){
            gcd = gcdNum2;
        }
            int aux = gcdNum2; 
            gcdNum2 = gcdNum1 % gcdNum2;
            gcdNum1 = aux;
    }

You do not need recursion to do this.

And be careful, it says that when a number is zero, then the GCD is the number that is not zero.

    while (gcdNum1 == 0) {
    gcdNum1 = 0;
}

You should modify this to fulfill the requirement.

I am not going to tell you how to modify your code entirely, only how to calculate the gcd.

Piragua

Answer 6

private static void GCD(int a, int b) {

    int temp;
    // make a greater than b
    if (b > a) {
         temp = a;
         a = b;
         b = temp;
    }

    while (b !=0) {
        // gcd of b and a%b
        temp = a%b;
        // always make a greater than bf
        a =b;
        b =temp;

    }
    System.out.println(a);
}

Bursarial

Answer 7

import java.util.Scanner;

class CalculateGCD 
{   
  public static int calGCD(int a, int b) 
  { 
   int c=0,d=0;  
   if(a>b){c=b;} 
   else{c=a;}  
   for(int i=c; i>0; i--) 
   { 
    if(((a%i)+(b%i))==0) 
    { 
     d=i; 
     break; 
    } 
   } 
   return d;  
  }  

  public static void main(String args[]) 
  { 
   Scanner sc=new Scanner(System.in); 
   System.out.println("Enter the nos whose GCD is to be calculated:"); 
   int a=sc.nextInt(); 
   int b=sc.nextInt(); 
   System.out.println(calGCD(a,b));  
  } 
 } 

Leanneleanor

Answer 8

Now, I just started programing about a week ago, so nothing fancy, but I had this as a problem and came up with this, which may be easier for people who are just getting into programing to understand. It uses Euclid's method like in previous examples.

public class GCD {
  public static void main(String[] args){
    int x = Math.max(Integer.parseInt(args[0]),Integer.parseInt(args[1]));    
    int y = Math.min(Integer.parseInt(args[0]),Integer.parseInt(args[1]));     
    for (int r = x % y; r != 0; r = x % y){
      x = y;
      y = r;
    }
    System.out.println(y);
  }
}

Circumbendibus