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