[算法笔记 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)$,依然太大,有没有更好的办法?

阅读更多