质数筛 埃拉托斯特尼筛法
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了质数筛 埃拉托斯特尼筛法,现在分享给大家,供学习和参考。文章包含842字,纯文字阅读大概需要3分钟。
教程信息
质数筛法:直接找出小于等于N的全部质数
埃拉托斯特尼筛法
简称埃氏筛或爱氏筛,由希腊数学家埃拉托斯特尼所提出
要得到自然数N以内的全部素数,必须把不大于根号N的所有素数的倍数剔除,剩下的就是素数。
①先用2去筛[2,N],即把2留下,把2的倍数剔除掉
②再用下一个质数,3筛[3,N],把3留下,把3的倍数剔除掉
③再用下一个质数,5筛[5,N],把5留下,把5的倍数剔除掉
④不断重复下去,直到循环到根号N
图片参考逻辑
实现代码:
#include <bits/stdc++.h> using namespace std; void check(int n,bool a[]) { //a[i]是bool类型数组,表示i是不是质数,true是质数,false不是质数 for (int i = 2; i <= sqrt(n); i++) //从2~sqrt(n)的话质数进不来有的 { if (a[i] == true) //没被筛掉,作为种子 { for (int j = i; i * j <= n; j++) //i的i倍、i+1倍……全部筛掉,i的2~i-1倍前面已经筛过了 { a[i * j] = false; //例如i=5 那么i的2/3倍分别在用2/3筛时已经筛过了 } } } } int main(){ int n=0; cin>>n; bool a[n]; for(int i=0;i<n;i++){ a[i]=true; } check(n,a); for(int i=0;i<n;i++){ if(a[i]==true&&i>=2){ cout<<i<<endl; } } return 0; }
执行结果:
埃氏筛可以从以下角度进行优化
①只筛奇数,因为除 2 以外的偶数都是合数,所以可以直接跳过它们。
②调整为欧拉筛法。
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供质数筛 埃拉托斯特尼筛法的全部内容,希望教程文章能够帮你了解学习质数筛 埃拉托斯特尼筛法,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-273.html