【欧拉计划】3. Largest prime factor
(本题取 $n=600851475143$)
【思路】在区间 $[2,n]$ 内倒序枚举 $n$ 的所有质因数,输出第一个遍历到的。时空复杂度分别为 $\mathcal O(n \sqrt n)$,$\mathcal O(1)$。
【优化 $1$】在原思路的基础上使用埃氏筛,时间复杂度优化为 $\mathcal O(n \ln \ln n+n)$;使用欧拉筛可优化为 $\mathcal O(n)$。
【优化 $2$】在原思路的基础上将区间缩小为 $[2,\sqrt n]$,时间复杂度优化为 $\mathcal O(n)$。
【优化 $3$】结合优化 $1,2$,时间复杂度可进一步优化至 $\mathcal O(\sqrt n)$(后面研究质数时不再提及质数判断法或埃氏筛,一律只保留欧拉筛)。
【优化 $4$】在【优化 $3$】的基础上,将循环改为正序。这样能减小时间复杂度的常数,同时将空间复杂度降为 $\mathcal O(1)$:
1 |
|
【欧拉计划】3. Largest prime factor