给定一个数 nnn,求其所有因数的集合,n≤1012n\leq10^{12}n≤1012。
显然有 Θ(n)\Theta(\sqrt n)Θ(n) 的做法。
那是不是也可以这么理解:
对于因数 x≤nx\leq\sqrt nx≤n,枚举 xxx 即可。
对于因数 x>nx>\sqrt nx>n,由于 x∣nx\mid nx∣n,也就有 nx∣n\frac{n}{x}\mid nxn∣n,枚举 nx\frac{n}{x}xn 即可。
可能这种理解方式挺若只的