How to write a simple Java program that finds the greatest common divisor between two numbers?
Solution 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.
Solution 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.
Solution 3
public static int GCD(int x, int y) {
int r;
while (y!=0) {
r = x%y;
x = y;
y = r;
}
return x;
}
Solution 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;
}
}
user1029481
Updated on July 24, 2022Comments
-
user1029481 almost 2 years
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); } }