质数因子

Read this in other languages: english.

质数 是一个比 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本身，再没有数可以被整除了。

Hardy-Ramanujan公式用于计算质数因子的个数

1917年，G.H Hardy和Srinivasa Ramanujan提出了一个定理，该定理指出，自然数 n 的不同素数的数 ω(n) 的正态次序是log(log(n))。

粗略地讲，这意味着大多数数字具有这个数量的质数因子。

References

• Prime numbers on Math is Fun
• Prime numbers on Wikipedia
• Hardy–Ramanujan theorem on Wikipedia
• Prime factorization of a number on Youtube