Someone please correct me if I'm wrong, but I guess the shortcut is something like this:
Z = X[1] * X[2] * X[3] * ... * X[n];
for i in (1..n-1) {
Z = Z/X[i];
g = GCD(X[i], Z);
if (g > 1) {
// check each other key to see which have g as a factor
for j in (j+1..n) {
if (X[j] % g == 0) {
log that keys i & j have g as a common factor;
}
}
}
Rather than having to run the inner loop for every iteration of the outer loop, it only has to run in the case where there is a common factor.
For instance, to check for common factors in [4, 13, 10] we initially compute Z = 4 * 13 * 10 = 520. Then we start with the first key, 4. Divide Z by 4 yielding 130. Do 4 and 130 have a common factor? gcd(4,130) = 2, so yes they do. We now check each remaining key individually (13 & 10) for divisibility by 2 and report which one(s) match, (in this case, 10). Then we continue with the second key, 13. Divide Z by 13 yielding 10. Do 13 & 10 have a common factor? No, they don't, and there are no more keys left to check, so we're done.
Yes that's correct, however you need not actually "log that keys i & j have g as a common factor;"
if g > 1 then just add x[i] to a list, after checking all in x, then just go through that much smaller list. ( even better would be to just group x[I] in a dictionary based on g)...
good example though.
For instance, to check for common factors in [4, 13, 10] we initially compute Z = 4 * 13 * 10 = 520. Then we start with the first key, 4. Divide Z by 4 yielding 130. Do 4 and 130 have a common factor? gcd(4,130) = 2, so yes they do. We now check each remaining key individually (13 & 10) for divisibility by 2 and report which one(s) match, (in this case, 10). Then we continue with the second key, 13. Divide Z by 13 yielding 10. Do 13 & 10 have a common factor? No, they don't, and there are no more keys left to check, so we're done.