0%

之前介绍了Eratosthenes筛法,时间复杂度是\(O(nloglogn)\)。比起最朴素的遍历法,这个时间复杂度已经不错了。然而,在建立质数表的时候,仍然会有重复计算。比如,我们遍历到\(2\)的时候,会筛掉指定范围中\(2\)的所有倍数,当然也就会筛掉\(12\)这个数,然后遍历到\(3\),同样也会筛掉\(12\)这个数,类似这种的重复计算还是挺多的。那么要怎样才能避免掉这些重复计算,优化时间复杂度呢?

Read more »