质数因子
行者、空山/2020-12-25 16:54
9 min read
定义
质数 是一个比 1 大的整数，且 不能由其它整数相乘得出。前几个质数是: 2, 3, 5, 7, 11, 13, 17, 19,依此类推。
如果我们能通过其它整数相乘得出，我们则称它为合数
Image source: Math is Fun
质数因子是那些相乘得到原始数的质数。例如39的质数因子是3和13，15的质数因子是3和5。
Image source: Math is Fun
正确计算所有的质数因子及其数量
这个方法将自然数n从i = 2除到i = n（仅按质数索引）。且每次循环后n的值被(n / i)的值替换。
在最坏的情况下，即循环从i = 2执行到 i = n，上述方法的时间复杂度为O(n)。时间复杂度其实可以从O(n)减少到O(sqrt(n))，通过减少循环的执行次数，从i = 2执行到 i = sqrt(n)。因为可以确认，当i大于sqrt(n)时，除了n本身，再没有数可以被整除了。
const primeFactors = (n)=>{
let nn = n;
const factors = [];
for (let factor = 2; factor <= Math.sqrt(nn); factor += 1) {
while (nn % factor === 0) {
nn /= factor;
factors.push(factor);
}
}
if (nn !== 1) {
factors.push(nn);
}
return factors;
}
Hardy-Ramanujan公式用于计算质数因子的个数
1917年，G.H Hardy和Srinivasa Ramanujan提出了一个定理，该定理指出，自然数 n 的不同素数的数 ω(n) 的正态次序是log(log(n))。
粗略地讲，这意味着大多数数字具有这个数量的质数因子。
const hardyRamanujan = (n) => {
return Math.log(Math.log(n));
}