我无法在Math Exchange或Stackoverflow上找到任何回答此特定问题的问题。 This是我发现的最相似的问题，但问题是如此糟糕，以至于答案完全不合适。
我试过在谷歌上寻找无济于事。我确实找到了this，但这个公式似乎非常低效，因此不够。例如，如果我们拿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 ......上述方法无论如何都不会有效。
我想要做的是找出找到任何两个数字的所有常见因素的最有效方法。
找到任意两个数字的公因子的最佳方法是什么？
我被指示在这个Math Exchange question中首先使用Euclidean algorithm找到最大的共同点，可以这样写：
const gcd = (a, z) => a ? gcd(z % a, a) : z
然后我被爱丽丝指示做两个数字的prime factorization，我可以反过来比较得到所有常见的素因子，从中可以导出所有常见的非素因子。值得注意的是，我甚至不确定如何将其编写为代码。
我想知道这是否比使用模数运算符（%）逐个检查最大公分母下面的所有整数更有效？
您可以使用此代码段来计算两个数字的公因数。
var a = 98, b = 56, cf = 0;
while (b != 0)
{
cf = b;
b = a % b;
a = cf;
}
console.log("CF: "+cf);
这个答案或多或少是在JS代码中实现@MarkDickinson的想法。重新思考主要思想是：
此代码不使用任何更复杂的想法，如Sieve of 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如何工作。基本上factors数组包含v0/v的所有因子的列表，即到目前为止我们已经找到的所有素因子的乘法因子。我们的想法是，如果我们有一些价值x及其所有factors，我们想知道p*x的所有因素，我们只需要复制factors并附加一个副本，每个已知因子乘以p。唯一的问题是，如果素数因子p具有多于1的多重性，为了避免重复，我们需要同时处理p，p^2，......而不是一个接一个。
以下算法应返回所有因子的数组。它应该比仅仅尝试划分所有值更快，因为它使用素数因子分解。
我做了以下：YouTube: Alle Teiler einer großen Zahl finden（视频是德语 - 只是关闭音频 - 没有必要理解内容）。用语言：我的代码计算给定数字的素因子，最后通过组合素因子（乘法）找到所有缺失的因子。
如果给定的素数不够，该算法将向素数模板数组添加更多素数。如果需要计算大量数字的因子，可以重用此数组。然而，在运行时计算新素数会减慢此算法的速度。最好将所有可能数字范围的素数添加到此数组中。
console.log(findAllFactors(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) => {
let primeCandidate = lastPrime + (lastPrime % 10 == 3 ? 4 : 2);
let sqrtNumber = Math.floor(Math.sqrt(primeCandidate));
let isPrime = true;
for(let i = 2; i < sqrtNumber + 1; i++) {
if (primeCandidate % i == 0) {
isPrime = false;
break;
}
}
if (!isPrime) addNextPrime(primeCandidate);
else primes.push(primeCandidate);
}
// returns array of prime factorisation
const findPrimeFactors = (currentFactor, highestFactor, primeFactors) => {
for(let i = 0; i < primes.length; i++) {
let mod = currentFactor % primes[i];
if (highestFactor == 0 && mod == 0) {
highestFactor = currentFactor / primes[i];
primeFactors.push(primes[i]);
primeFactors = findPrimeFactors(currentFactor / primes[i], highestFactor, primeFactors);
return primeFactors;
} else {
if (primes[i] < highestFactor) {
if (i == primes.length - 1) {
addNextPrime(primes[primes.length - 1]);
}
if (mod == 0) {
primeFactors.push(primes[i]);
primeFactors = findPrimeFactors(currentFactor / primes[i], highestFactor, primeFactors);
return primeFactors;
}
} else return primeFactors;
}
}
}
// Calculates the missing factors by combining prime factors
const findAllFactors = (input) => {
let factors = findPrimeFactors(input, 0, []);
let primeCount = factors.length;
let combinedFactor;
for (let i = 0; i < primeCount - 1; i++) {
for (let j = i + 1; j < primeCount; j++) {
if (j == i + 1) combinedFactor = factors[i] * factors[j];
else combinedFactor *=factors[j];
factors.push(factors[i] * factors[j]);
factors.push(combinedFactor);
}
}
factors.push(1);
factors = factors.sort((a, b) => a - b).filter((value, index, array) => index == array.indexOf(value));
return factors;
}
console.log(findAllFactors(2252));
另外：计算两个给定数字的公因子：
const commonFactors = (a, b) => {
let aFactors = findAllFactors(a);
let bFactors = findAllFactors(b);
// still optimizable:
return aFactors.filter(value => bFactors.includes(value));
}
console.log(commonFactors(24, 96));
我想我已经找到了一种简洁有效的方法来做到这一点。
我相信odd gdc部分可以通过不断地将r分成“一半”来改善。是否有任何数学家或聪明人可以验证这一点？
const cf = (a,z) => {
const gcd = (a, z) => a ? gcd(z % a, a) : z
const g = gcd(a,z)
const cfarr = g > 1 ? [1, g] : [1]
let c
console.log(g)
if (g%2 > 0) {
// odd gcd
c = 3
let r = Math.floor(g/2)
r%2 === 0 ? r-=1 : r-=2
while (c < g) {
if (g%c === 0) cfarr.push(c)
c+=2
}
} else {
// even gcd
c = 2
while (c < g/2) {
let n = g/c
if (c <= n && n%1 === 0) cfarr.push(c,n)
c++
}
}
console.log(cfarr+`
`)
}
cf(9,27)
cf(333,2120)
cf(550,790)
cf(1850,2018)请让我知道您的想法，如果您看到任何改进或可以以任何方式改进它！