Most efficient way to find all common factors of any two numbers

Question

I have not been able to find any questions on Math Exchange nor Stackoverflow that answer this specific question. This is the most similar question that I have found, but the question is so poorly constructed that the answer is completely inadequate.

I have tried looking on Google to no avail. I did find this, but the formula seems incredibly inefficient and therefore insufficient. For instance, if we took the number 21...

21 % 1 = 0
21 % 2 = 1
21 % 3 = 0
21 % 4 = 1
21 % 5 = 1
21 % 6 = 3
21 % 7 = 0
...

Now imagine finding the common factors of numbers much greater than 21, such as 2,252 and 4,082... The method above would not be efficient whatsoever.

What I am trying to do is figure out the most efficient way to find all of the common factors of any two numbers.

What is the most optimal method to find the common factors of any two numbers?

I was instructed in this Math Exchange question to first find the greatest common denominator by using the Euclidean algorithm, which can be written like so:

const gcd = (a, z) => a ? gcd(z % a, a) : z

I was then instructed by Alice to do a prime factorization of both numbers, which I can in turn compare to get all of the common prime factors, from which all common non-prime factors can be derived. Notably, I am not even sure how to write this as code just yet.

I am wondering whether or not this is any more efficient than simply using the modulus operator (%) to check all of the integers below the greatest common denominator one-by-one?

Answer 1

The following algorithm should return an array of all factors. It should be faster than just trying to divide all values because it uses prime factorization.

I did the following: YouTube: Alle Teiler einer großen Zahl finden (The video is in german - just turn audio off - it's not necessary to understand the content). In words: My code calculates the prime factors of a given number and finally finds all missing factors by combining the prime factors (multiplication).

The algorithm will add more primes to the primes template array if the given primes are not enough. If you need to calculate the factors of a huge amount of numbers, this array can be reused. Nevertheless calculating new primes at runtime will slow down this algorithm. It would be better to add all primes of your possible numbers range to this array.

console.log(findAllFactors(2252)) should return [ 1, 2, 4, 563, 1126, 2252 ]

EDIT: I have added one more function that compares the factors of two given numbers. It returns an array of their common factors.

Calculating all factors of a given number:

// The more primes you add to this array the lower is the 
// prohability for calculating new primes at runtime
// (minimum primes in array: [2, 3, 5])
const primes = [ 2, 3, 5, 7, 11, 13, 17, 19 ];


// Adds next prime to array "primes"
const addNextPrime = (lastPrime) => {
    const primeCandidate = lastPrime + (lastPrime % 10 === 3 ? 4 : 2);
    const sqrtNumber = Math.floor(Math.sqrt(primeCandidate));
    for(let i = 2; i < sqrtNumber + 1; i++) {
        if (primeCandidate % i === 0) {
            return addNextPrime(primeCandidate);
        }
    }
    primes.push(primeCandidate);
}

// returns array of prime factorization
const findPrimeFactors = (currentFactor, highestFactor = 0, primeFactors = []) => {
    for(let i = 0; i < primes.length; i++) {
        const mod = currentFactor % primes[i];
        if (highestFactor === 0 && mod === 0) {
            highestFactor = currentFactor / primes[i];
            primeFactors.push(primes[i]);
            return findPrimeFactors(currentFactor / primes[i], highestFactor, primeFactors);
        } else {
            if (primes[i] <= highestFactor) {
                if (i === primes.length - 1) {
                    addNextPrime(primes[primes.length - 1]);
                }
                if (mod === 0) {
                    primeFactors.push(primes[i]);
                    return findPrimeFactors(currentFactor / primes[i], highestFactor, primeFactors);
                }
            } else if (highestFactor) {
                return primeFactors;
            }
        }
    }
}

// Calculates the missing factors by combining prime factors
const findAllFactors = (input) => {
    const factors = findPrimeFactors(input);
    const primeCount = factors.length;
    let combinedFactor;
    for (let i = 0; i < primeCount - 1; i++) {
        for (let j = i + 1; j < primeCount; j++) {
            combinedFactor = (j === i + 1) ? factors[i] * factors[j] : combinedFactor * factors[j];
            factors.push(factors[i] * factors[j]);
            factors.push(combinedFactor);
        }
    }
    factors.push(1);
    return factors.sort((a, b) => a - b).filter((value, index, array) => index === array.indexOf(value));
}

console.log(findAllFactors(2252));

Additionally: Calculating common factors of two given numbers:

const commonFactors = (a, b) => {
    const aFactors = findAllFactors(a);
    const bFactors = findAllFactors(b);
    // still optimizable:
    return aFactors.filter(value => bFactors.includes(value));
}

console.log(commonFactors(24, 96));

Answer 2

This answer is more or less implementation of @MarkDickinson ideas in JS code. To re-iterate the main ideas are:

1. Ignore the two numbers problem. First find GCD and then factorize it.

2. When doing factorization it makes sense to find only prime divisors and calculate others

3. During the search for prime divisors it is enough to search up to the square root of the number. Moreover as new primes are found it makes sense to lower the square root estimate by removing (i.e. dividing by) known prime factors.

This code doesn't use any more sophisticated ideas such as Sieve of Eratosthenes. So here is the code:

const gcd = (a, b) => {
    const impl = (ai, bi) => ai ? impl(bi % ai, ai) : bi;
    // handle also case when a or b is 0 from the beginning
    return impl(Math.min(a, b), Math.max(a, b))
};

const factor = (v0) => {
    let v = v0;
    let factors = [1];

    const addFactors = (fs) => {
        if (fs.length > 0) {
            // pre-allocate space
            let newFactors = new Array(factors.length * fs.length);
            let o = 0;
            for (let i = 0; i < factors.length; i++)
                newFactors[o++] = factors[i];

            for (let i = 0; i < factors.length; i++) {
                for (let j = 0; j < fs.length; j++) {
                    newFactors[o++] = factors[i] * fs[j];
                }
            }
            factors = newFactors;
        }
    };

    const addFactorPows = (f) => {
        // find all powers of the factor
        // Example; v = 12, f = 2
        // We want pows to be [2, 4]
        // This is important for addFactors to work correctly
        let p = 1;
        let pows = [];

        while (v % f === 0) {
            v /= f;
            p *= f;
            pows.push(p);
        }
        addFactors(pows);
        return (pows.length !== 0);
    };

    addFactorPows(2);

    let s = Math.floor(Math.sqrt(v));
    for (let i = 3; i <= s; i += 2) {
        if (addFactorPows(i)) {
            s = Math.floor(Math.sqrt(v));
        }
    }
    // probably add the last prime, unless there was a perfect square and v = 1
    if (v !== 1)
        addFactorPows(v);

    return factors.sort((a, b) => (a - b));
};

const commonFactors = (a, b) => {
    const g = gcd(a, b);
    return factor(g);
};

Probably the most complicated idea here is how addFactorPows/addFactors work. Essentially factors array holds the list of all factors of the v0/v i.e. factors of the multiplication of all the prime factors we've already found so far. The idea is that if we have some value x and all its factors and we want to know all factors of p*x, we just need to copy factors and also append to it a copy with each known factor multiplied by p. The only catch is that to avoid duplication if a prime factor p has multiplicity more than 1 we need to process p, p^2, ... at the same time instead of one by one.

Answer 3

you may use this code segment for calculating Common factors of two number.

var a = 98, b = 56, cf = 0;
while (b != 0)
 {
  cf = b;
  b = a % b;
  a = cf;
 }
console.log("CF: "+cf);