如果预处理出 $n$ 以内每个数的最小质因子，那么可以在 $O(\log n)$ 时间内完成任意一个不超过 $n$ 的整数的质因数分解。

线性筛（欧拉筛）能够保证每个合数只被其最小质因子筛掉一次，这一性质依赖于唯一分解定理。

唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

唯一分解定理是埃氏筛时间复杂度为 $O(n \log\log n)$ 的根本原因。