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

Question

我无法在 Math Exchange 或 Stackoverflow 上找到任何可以回答这个特定问题的问题。这是我发现的最相似的问题，但问题的结构太差，答案完全不够。

我试过在谷歌上搜索无济于事。我确实发现了这一点，但该公式似乎效率低下，因此不足。例如，如果我们取数字 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 指示我对两个数字进行质因数分解，然后我可以比较这些数以得到所有常见的质因数，从中可以推导出所有常见的非质数。值得注意的是，我什至不确定如何将其编写为代码。

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

Answer 1

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

\n

我做了以下操作：YouTube：Alle Teiler einer gro\xc3\x9fen Zahl finden（该视频是德语 - 只需关闭音频 - 无需理解内容）。换句话说：我的代码计算给定数字的质因数，并最终通过组合质因数（乘法）找到所有缺失的因数。

\n

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

\n

console.log(findAllFactors(2252))应该返回[ 1, 2, 4, 563, 1126, 2252 ]

\n

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

\n

计算给定数字的所有因数：

\n

// The more primes you add to this array the lower is the \n// prohability for calculating new primes at runtime\n// (minimum primes in array: [2, 3, 5])\nconst primes = [ 2, 3, 5, 7, 11, 13, 17, 19 ];\n\n\n// Adds next prime to array "primes"\nconst addNextPrime = (lastPrime) => {\n    const primeCandidate = lastPrime + (lastPrime % 10 === 3 ? 4 : 2);\n    const sqrtNumber = Math.floor(Math.sqrt(primeCandidate));\n    for(let i = 2; i < sqrtNumber + 1; i++) {\n        if (primeCandidate % i === 0) {\n            return addNextPrime(primeCandidate);\n        }\n    }\n    primes.push(primeCandidate);\n}\n\n// returns array of prime factorization\nconst findPrimeFactors = (currentFactor, highestFactor = 0, primeFactors = []) => {\n    for(let i = 0; i < primes.length; i++) {\n        const mod = currentFactor % primes[i];\n        if (highestFactor === 0 && mod === 0) {\n            highestFactor = currentFactor / primes[i];\n            primeFactors.push(primes[i]);\n            return findPrimeFactors(currentFactor / primes[i], highestFactor, primeFactors);\n        } else {\n            if (primes[i] <= highestFactor) {\n                if (i === primes.length - 1) {\n                    addNextPrime(primes[primes.length - 1]);\n                }\n                if (mod === 0) {\n                    primeFactors.push(primes[i]);\n                    return findPrimeFactors(currentFactor / primes[i], highestFactor, primeFactors);\n                }\n            } else if (highestFactor) {\n                return primeFactors;\n            }\n        }\n    }\n}\n\n// Calculates the missing factors by combining prime factors\nconst findAllFactors = (input) => {\n    const factors = findPrimeFactors(input);\n    const primeCount = factors.length;\n    let combinedFactor;\n    for (let i = 0; i < primeCount - 1; i++) {\n        for (let j = i + 1; j < primeCount; j++) {\n            combinedFactor = (j === i + 1) ? factors[i] * factors[j] : combinedFactor * factors[j];\n            factors.push(factors[i] * factors[j]);\n            factors.push(combinedFactor);\n        }\n    }\n    factors.push(1);\n    return factors.sort((a, b) => a - b).filter((value, index, array) => index === array.indexOf(value));\n}\n\nconsole.log(findAllFactors(2252));\n

\n

另外：计算两个给定数字的公因数：

\n

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

\n