Java

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

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 a
if( (b%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.