Shortest Method for finding if there is a common factor between two numbers

I want to know the most efficient algorithm in terms of execution time for finding if there is any common factor exist (except 1) between two numbers. The only method comes to my mind is to find the GCD of two numbers or more efficiently check whether the two numbers are even or not then find the GCD.

4 Answers

you might take a look at this post:

I don't think there is a way to be sure whether a method is really "the fastest". All you can do is compare different implementations and try alternatives...

EDIT: btw: better do a quick search on google before posting here; found another interesting link, somebody asking the same question!:

int a = 20, b = 5, GCD = 0;
while (b != 0)
{ GCD = b; b = a % b; a = GCD;
}
printf("%d",GCD);

Following should do - Is there a way to optimize?

public boolean hasCommonFactor(int x, int y) { int min = Math.min(x, y); int max = Math.max(x, y); for (int i = 2; i <= min; i++) { if (min % i == 0 && max % i == 0) { return true; } } return false; }

This question has no sense without the boundaries of both numbers. I can imagine two possible approaches:

First approach is the calculation of the Greatest Common Divisor (GCD), following the Euler algorithm. This procedure is well-known and gives the GCD is a reasonable amount of time (I believe ±O(log n).

The second approach is based on the Sieve of Eratosthenes: first create that sieve, beginning with (2, 3, 5, 7, 11, 13, 17, 19, ...). You go through this sieve up to ±min(sqrt(a)+1,sqrt(b)+1) until you find a common factor. Obviously best is to have a prepopulated sieve.

I personally think that the best approach is a combination of both approaches: start with a prepopulated sieve, generate it further until a certain point and in case this does not yield a result, switch to the general GCD approach. But how to define the "certain point", based on the size of the numbers you're investigating, that's the real question.