[算法笔记3]Codeforces - 1139 D. Steps to One

如何求出1-n每个数的全部因子?
在继续往下阅读之前,请先想一想,如果给定一个$n,n\leq100000$,让你求出1~n的全部因子,你需要如何实现?要编写多少行代码?复杂度如何?

可能会这么考虑,如果对于每个数$x$,枚举1~n逐一判断每个数是否是$x$的因子,复杂度为$\mathcal{O}(n^2)$,显然是不可接受的,即使枚举到$\sqrt n$,复杂度也有$\mathcal{O}(n \sqrt n)$,依然太大,有没有更好的办法?

阅读更多