我刚刚学习了如何使用这个算法来找到一个数字的质因数。该算法基本上是这样运作的:
void printPrimeFactors(N) {
while N is even
print 2 as prime factor
N = N/2
// At this point N is odd
for all the ODDS i from 3 to sqrt(N)
while N is divisible by i
print i as prime factor
N = N / i
if N hasn't been divided by anything (i.e. it's still N)
N is prime
}
一切都很清楚,但我不确定如何计算上述程序的大O复杂度。
作为最昂贵的操作(我想),除法可能是最坏情况下最多有log(N)次,但我并不完全确定。
sqrt(N)
次检查,而所有的检查结果都是false。 - biziclopODDS i
的主循环中,每次成功迭代后,您可以将上限从sqrt(N)
减少到sqrt(N /已知因子的乘积)
。在实现之前,我建议您研究“筛法”和相关算法。 - MichaelN
的更新,上限也会下降。当然,即使你仔细调整你的上限并跳过已知的合数(将算法转化为基本的 Erathosthenes 筛法),该算法仍远非最优。 - biziclop