找到任意两个数的所有公因数的最有效方法

Question

我找不到任何关于数学交换和堆栈溢出的问题来回答这个特定问题。这是我发现的最相似的问题，但这个问题构造得太差，答案完全不充分。

我尝试过在谷歌上寻找无济于事。我确实发现了这一点，但这个公式似乎效率低下，因此不够。例如，如果我们取数字21...

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

现在想象一下找到远大于21的数字的共同因素，例如2，252和4，082...上述方法没有任何效率。

我想做的是找出最有效的方法来找到任何两个数字的所有公因数。

求任意两个数的公因数最优化的方法是什么？

在这个数学交换问题中，我被指示首先使用欧几里得算法找到最大的共同点，它可以这样写：

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

然后，Alice指示我对这两个数字进行质因数分解，我可以反过来进行比较，以获得所有的公共质因数，从中可以导出所有的公共非质因数。值得注意的是，我甚至不确定如何将它写成代码。

我想知道这是否比简单地使用模数运算符(< code>%)逐个检查最大公分母以下的所有整数更有效？

Answer 1

您可以使用此代码段来计算两个数的公因数。

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

Answer 2

下面的算法应该返回一个包含所有因子的数组。它应该比仅仅尝试除以所有值更快，因为它使用素数分解。

我做了以下事情：YouTube:Alle Teiler einer großen Zahl finden（视频是德语的，只需关闭音频，不需要理解内容）。简而言之：我的代码计算给定数字的素因子，最后通过组合素因子（乘法）找到所有缺失的因子。

如果给定的素数不够，该算法将向素数模板数组添加更多的素数。如果需要计算大量数字的因子，这个数组可以重用。然而，在运行时计算新的素数会降低算法的速度。最好把你可能的数字范围内的所有素数都加到这个数组里。

控制台.log（查找全部因素（2252））应返回 [ 1， 2， 4， 563， 1126， 2252 ]

编辑：我又添加了一个函数来比较两个给定数字的因子。它返回它们的公共因子数组。

计算给定数字的所有因子:

// 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));

另外：计算两个给定数字的共同因子：

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 3

这个答案或多或少是@MarkDickinson思想在JS代码中的实现。重新迭代主要思想是：

>

忽略两个数字问题。首先找到GCD，然后将其分解。

当进行因式分解时，只找到素数因子并计算其他因子是有意义的

在搜索素数因子的过程中，搜索到数的平方根就足够了。此外，当发现新的素数时，通过删除（即除以）已知的素数因子来降低平方根估计是有意义的。

这段代码没有使用任何更复杂的想法，例如Eratosthenes筛子。所以这是代码：

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);
};

可能这里最复杂的想法是addFactorPows/addFactors是如何工作的。本质上，因素数组保存了v0/v的所有因素的列表，即我们迄今为止已经找到的所有素数因素的乘法因素。这个想法是，如果我们有一些值x及其所有因素，并且我们想知道p*x的所有因素，我们只需要复制因素并附加一个副本，每个已知因素乘以p。唯一的问题是，为了避免重复，如果素因子p的多重性大于1，我们需要同时处理p，p^2，…而不是一个接一个。