What is a Java program that finds the greatest common factor of two integers?

Answer 1

The easiest way to find the greatest common denominator of two integers with a computer program is to use the Euclidean algorithm. Of the most popular methods of finding the GCD of two numbers, the Euclidean algorithm does it with the least amount of work and requires the least amount of code.

In order to understand the Euclidean algorithm, you'll need to know a few division terms:

• The dividend is the number to be divided.
• The divisor is the number being divided by.
• The quotient is the number of times the divisor divides into the dividend.
• The remainder is the amount "left over" when the divisor cannot go into the dividend an integral number of times.

18A divided by 12B gives a quotient of 1C and a remainder of 6D.

A is the dividend, B is the divisor, C is the quotient, and D is the remainder.

The Euclidean algorithm works like this:

1. Check if either of the two integers is 0. If so, there is no solution (Ø), as a number cannot share a GCD with zero. Besides, division by zero is a big no-no.
2. Check if either of the two integers is 1. If so, 1 is the GCD.
3. Divide the larger of the two integers by the smaller.
4. Divide the divisor of the previous division operation by the remainder of the previous operation.
5. Repeat step four until the remainder equals zero. When the remainder equals zero, the divisor of the last operation is the GCD.

If you still don't get it, try looking at the Euclidean algorithm in action:

Find the GCD of 84 and 18.

1. Check to see if either 84 or 18 is equal to 0. Nope. Continue on...
2. Check to see if either 84 or 18 is equal to 1. Nope. Continue on...
3. Since 84 is larger than 18, divide 84 by 18. Quotient is 4, remainder is 12.
4. Take the divisor of the last operation (18) and divide it by the remainder of the last operation (12). Quotient is 1, remainder is 6.
5. Take the divisor of the last operation (12) and divide it by the remainder of the last operation (6). Quotient is 2, remainder is 0.
6. When the remainder is 0, the divisor of the last operation is the GCD. So the GCD in this case is 6.

You should now have a good grasp of how the Euclidean algorithm works. Now we need to turn it into code. We'll need three variables, all of them integers:

int divisor, dividend, remainder;

The purpose of the variables is self-explanatory. Next, we need to make a few decisions. We need to decide if the dividend or the divisor is 0. If that test is passed, then we need to decide if the dividend or the divisor is 1. If that test is passed, then we need make sure that dividend is larger than divisor.

if(dividend 1) {

printf("The GCD is 1.\n");

}

// Make sure the dividend is greater than the divisor.

if(divisor > dividend) {

remainder = dividend;

dividend = divisor;

divisor = remainder;

}

// Calculate the GCD.

while(remainder != 0) {

remainder = dividend % divisor;

dividend = divisor;

divisor = remainder;

}

// Display the answer to the user.

printf("The GCD is %i.\n", dividend);

}

And the GCD lived happily ever after. The end.

Answer 2

If you're interested only in solving the problem, and not in performance, then the simplest way is to simply start by trying to divide one number by the other. If they divide evenly, then that number is the GCF, else subtract it by one and keep trying.

public static int GCF(int a, int b) {

// current will start off as the lesser of the two numbers.

// after each attempt to find a common factor, decrement current

int current = Math.min(a,b);

// loop until current is 1. if this happens, all other possibilities have been

// eliminated and thus a and b share no common factors other than 1

while( current > 1) {

// check factors

if( (a%current) 0) { // check if current is a factor of b

// if current is a factor of both a and b, then current

// is the GCF and we can break out of the loop

break;

}

}

--current;

}

return current;

}

// or for a slightly more concise version...

public static int GCF(int a, int b) {

for(int current = Math.min(a,b); current > 1; --current) {

if( (a%current)==0 && (b%current==0) ) {

return current;

}

}

return 1;

}

Again, both of these algorithms perform in O(n) time, which can be quite terrible for large numbers and/or slow machines.