分解素数中的数字

Question

如何找到区间内的数（从 1 到 给定的数 ）分解为质数时具有最大数量。

示例：

输入：9

输出：8

解释：

8 = 2 * 2 * 2（3 个素数）

7 = 7 * 1（1 个素数）

6 = 3 * 2（2 个素数）

以此类推...最后，我们会看到8在分解中的素数最多

规格：

如果有几个数字在分解中具有相同数量的素数，return其中最大的一个。

Answer 1

好的，我想我明白你的要求了。

这是一个简单的脚本来完成您所要求的。

//source of this function: https://jsfiddle.net/JamesOR/RC7SY/

function getAllFactorsFor(remainder) {
    var factors = [], i;

    for (i = 2; i <= remainder; i++) {
        while ((remainder % i) === 0) {
            factors.push(i);
            remainder /= i;
        }
    }

    return factors;
}

function calculate(x) {

    lastFactorCount = 0;
    highestNumber = 0;

    while (x) {
        currentCount = getAllFactorsFor(x).length;

        if (currentCount > lastFactorCount) {
            lastFactorCount = currentCount;
            highestNumber = x;
        }

        x--;
    }

    return highestNumber;
}

console.log(calculate(7)); //output: 6
console.log(calculate(11)) //output: 8

这通过了你给出的两个测试用例。我从我发现的 jsfiddle 中借用了 getAllFactorsFor() 函数，因为我们不需要重新发明任何东西 ;)

calculate() 函数接受一个输入数字，然后遍历从 x 到 0 的每个数字，计算它有多少个因子，并在每次迭代中递减 x 时跟踪最后一个因子计数.

最后它输出具有最高因子计数的数字。简单。

希望对您有所帮助！！

Answer 2

请注意，在 2 和 3 之后，下一个质数是 5，它大于 2*2（很明显）。因此，对于质因数的数量，使用 2*2 总是比任何更高的质数更好。以 2 为素数的数量最多的数仍然小于或等于 2 ** Math.floor(Math.log2(num))。我们唯一需要检查的是，用 3 替换最后一个质因数 2 是否仍会低于该数字，因为这可能会发生，并且会产生更大的数字。再次注意，使用一个以上的 3 将是 3*3 = 9 > 8 = 2*2*2，这不能再次成为解决方案。所有这些共同得出解决方案应该只是

const f = num => {
  let twoEnd = 2 ** Math.floor(Math.log2(num));
  let threeEnd = twoEnd / 2 * 3;
  return threeEnd <= num ? threeEnd : twoEnd;
}

根据具体情况，可能需要对小于 2 的数字进行一些处理。

分解素数中的数字

Decompose a number in prime numbers

javascript

arrays

primes

loops

factorization