【欧拉计划】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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
}

【欧拉计划】3. Largest prime factor

https://hensier.github.io/projecteuler/3/

作者

hensier

发布于

2022-05-01

更新于

2023-01-02

许可协议

评论