大家好,又见面了,我是你们的朋友全栈君。
在刚接触编程语言时,对于寻找素数,第一时间想到的便是二重循环暴力查找,其复杂度O(n^2),通过循环中只判断到根号n可以优化一些,不过复杂度也达不到预期。在数论的学习中,我学到了埃氏筛法,O(nloglogn)的算法,而在一些数据范围达到1e7这样的题目中,也很难让人满意,于是我便学习了欧拉筛法,也即 O(n)的线性筛法。
int visit[maxn];
void Prime(){
mem(visit,0); //初始化都是素数
visit[0] = visit[1] = 1; //0 和 1不是素数
for (int i = 2; i <= maxn; i++) {
if (!visit[i]) { //如果i是素数,让i的所有倍数都不是素数
for (int j = i*i; j <= maxn; j += i) {
visit[j] = 1;
}
}
}
这里有一个小优化,j 从 i * i 而不是从 i + i开始,因为 i*(2~ i-1)在 2~i-1时都已经被筛去,所以从i * i开始。
int prime[maxn];
int visit[maxn];
void Prime(){
mem(visit,0);
mem(prime, 0);
for (int i = 2;i <= maxn; i++) {
cout<<" i = "<<i<<endl;
if (!visit[i]) {
prime[++prime[0]] = i; //纪录素数, 这个prime[0] 相当于 cnt,用来计数
}
for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
// cout<<" j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl;
visit[i*prime[j]] = 1;
if (i % prime[j] == 0) {
break;
}
}
}
}
发现i在消去合数中的作用是当做倍数的。
对于欧拉筛法的学习是先从接触到题开始的,研究了一天才弄懂,很惭愧,再次遇到题也不见得可以游刃有余的解决,在此与大家共勉,学海无涯。 附上题目 :https://nanti.jisuanke.com/t/30999 (大佬眼中的签到题)
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/125441.html原文链接:https://javaforall.cn