质数筛 欧拉筛法/线性筛法
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了质数筛 欧拉筛法/线性筛法,现在分享给大家,供学习和参考。文章包含1634字,纯文字阅读大概需要5分钟。
教程信息
质数筛法:直接找出小于等于N的全部质数
线性筛法/欧拉筛法
埃氏筛法中有些合数会被反复标记,因此也就浪费了一些运算时间,可以只让合数的最小质因数筛它
①每次循环把所有的已知质数都作为筛子b[0~p]
②当前循环的数i如果是质数就加入筛子,如果不是就作为倍数乘上全部的筛子进行筛数a[i*b[0~p]]
③在筛数的过程中,如果发现当前数是某个筛子的倍数i%b[j]==0
那么其它和其他筛子的乘积i*b[j+1~p]必定是这一筛子b[j]的倍数,在后续一定会被b[j]*更大的i筛
数据举例:
实现代码:
#include <bits/stdc++.h> using namespace std; const int N = 120; int vis[N]; //0表示素数,1表示非素数 int prime[N]; //只在这个函数有作用 int x = 0; void Euler_prime() //欧拉筛法 { for (int i = 2; i <= N; i++) { if (!vis[i]) { prime[x] = i; // 辅助理解 // cout<<"prime"<<x<<"-"<<i<<endl; // printf("prime%d-%d\n",x,i); x++; } for (int j = 0; j < x; j++) { if (i * prime[j] > N) { break; } vis[i * prime[j]] = 1; //printf("%d-[%d]%d-%d\n",i,j,prime[j],i*prime[j]); if (i == 4) { int aa = 1; } if (i == 5) { int aa = 1; } if (i % prime[j] == 0) { //如果当前数能被某个质数整除,直接跳出 break; //说明这个数和其他质数的倍数i*b[j+1~p],一定能被质数b[j]整除 } //这就说明不需要通过a[i+b[j+1~p]]去筛,未来会a[i(更大的i)*b[j]]去筛 } // 辅助理解 // printf("\n\n"); } // 辅助理解 // for(int i=0;i<N;i++){ // if(vis[i]==0&&i>=2){ // cout<<i<<endl; // } // } // 辅助理解 for (int i = 0; i < x; i++) { //if (vis[i] == false) { cout << prime[i] << endl; //} } } int main() { Euler_prime(); return 0; }
执行结果:
线性筛还有以下功能
①可以求出每个数的最小质因数即令i跳出循环的b[j]就是i的最小质因数
②可以和算数基本定理的推理结合,求一个数的因数个数和因数和
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供质数筛 欧拉筛法/线性筛法的全部内容,希望教程文章能够帮你了解学习质数筛 欧拉筛法/线性筛法,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-274.html