【欧拉计划】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)$：

#include<stdio.h>
long long n=600851475143;
int main()
{
    for(long long i=3;i*i<=n;i+=2)
    {
        while(n%i==0)
        {
            n/=i;
            if(n==1)
            {
                printf("%lld",i);
                return 0;
            }
        }
    }
    printf("%lld",n);
    return 0;
}