关键词：
内容摘要：
- 明确素数到底是啥数。
- 埃式筛法是干嘛用的。
- 利用java实现埃式筛法的思路。
- 利用埃式筛法解决PAT_1013_B 题。
- 筛法的改进。
素数(prime number)到底是啥数：
定义:
在大于1的自然数中，除了1和它本身以外不能再被其他数所整除。
实例化定义:
- 3是素数，因为它不可以被除了“1”以及自身“3”之外的数所整除。
- 10不是素数，因为它除了“1”以及自身“10”之外，还可以被"2"，“5”等数字所整除，所以他不是素数。我们也叫他“合数”(composite number)。
需要注意:
- 2是最小的素数。
- "素数"和"质数"是同一样东西。
埃式筛法是干什么用的：
作用：
从一堆自然数里面，找出这一堆自然数里面的所有的素数。
实例化：
- 前提：a[]=1,2,3,4,5,6,7,8,9...29，prime[]=。
- 通过: 埃式筛法从数组a中筛选出所有的素数，并且把他们放进数组prime[]中。
- 得到：prime[]=2,3,5,7,11,13,19,23,29。
利用java实现埃式筛法的思路：
首先明确算法主要的依据以及两个前提：
主要的依据：任何一个合数，一定有比他小的素数因子。（大家可以利用小时候学的分解自然数的过程去理解一下这句话）
- 默认2是已知的最小的素数
- 任何素数的倍数都不是素数，比如已经"2"是素数，但是2的倍数，例如4,6,8,10,12...都一定不是倍数,因为"倍数"就是可以整除这个数的因子。
下面是寻找n = 50以内的所有素数的实例：
我们首先建立了一个数字由2到50的数组。
然后我们确定2是素数，所以我们标记了所有2的倍数为非素数。
因为3没有在上一步被标记，所以我们得出3是素数，然后我们标记所有3的倍数为非素数
然后我们来到没有被标记的数字5，然后标记所有5的倍数为非素数
我们继续，然后得到
所以，素数应该是这里面没有被标记的元素：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.
（以上Figure由Krishan Kumar提供）
转化成代码的几个关键部分：
1.利用boolean类型的素组去标记非素数
2.算法由嵌套的两层循环组成
- 外层：寻找未被标记的元素（素数）
- 内层：把素数的倍数标记为合数(composite)
java代码（找出自然数upperBound内，包括upperBound的所有的素数，并且把它们输出）
1 public void runEratosthenesSieve(int upperBound) 2 int upperBoundSquareRoot = (int) Math.sqrt(upperBound); 3 /*这里取平方是因为通过数学推理可以知道只需要判断到upperBound的上界即可。 4 第一次写的读者可以把循环的次数设置成upperBound，便于理解*/ 5 boolean[] isComposite = new boolean[upperBound + 1]; 6 //这个boolean类型的数组是为了标记upperBound以内的自然数 7 8 for (int m = 2; m <= upperBoundSquareRoot; m++) 9 if (!isComposite[m]) 10 System.out.print(m + " "); 11 for (int k = 2 * m; k <= upperBound; k += m)
12 isComposite[k] = true; 13 14 15 for (int m = upperBoundSquareRoot; m <= upperBound; m++) 16 if (!isComposite[m]) 17 System.out.print(m + " ")； 18
题意：输出第M~N个素数。
思路：利用筛法把素数表打印至第N个素数，然后按格式输出。
java代码
1 class Prime1 2 private int maxn =100010; 3 private int a[] =new int[maxn]; 4 5 void isPrime(int n) 6 boolean flag[] = new boolean[maxn]; 7 int index=0; 8 for(int i=2;i<maxn;i++) 9 if(index>=n) break;//无需找出第n个素数后的素数 10 if(! flag[i]) 11 a[index]=i; 12 index++; 13 for (int j=2*i;j<maxn;j+=i) 14 flag[j]=true; 15 16 17 18 19 20 void outprint(int m,int n) 21 int count=0; 22 isPrime(n); 23 for(int i=m-1;i<n;i++) 24 if(count%10!=0&&i!=n-1) 25 System.out.print(a[i]+" "); 26 else 27 System.out.println(); 28 29 30 31
改进筛法：
*我们注意到，算法中标记倍数可以从已找到的素数的平方开始标记（而不是从它的两倍开始）
对于 m = 2,原先的算法标记了
2*2 3*2 4*2 5*2 6*2 7*2 8*2 ...
对于 m = 3,原先的算法标记了
2*3
2*3这一步在m = 2的时候已经被标记
对于 m = 5，
2*5 3*5 4*5（= 10*2）
已经在m = 2以及m = 3的时候被标记了
这里缺少了严格的数学证明，有兴趣的读者朋友可以自己证明。
对范围在2~100的数应用改进后埃式筛法筛选出这里面的所有素数的过程：
装有2~100自然数的数组的最初状态。
2是素数，标记所有2的倍数。从4开始。
3在上一步没有被标记，所以3是素数。标记所有3的倍数，从9开始。
5是素数，标记所有5的倍数，从25开始
7是素数，标记所有7的倍数，从49开始
11的平方，超过了100，在数组里面所有没有被标记的数字都是素数
最终得到的结果
java代码（找出自然数upperBound内，包括upperBound的所有的素数，并且把它们输出）
1 public void runEratosthenesSieve(int upperBound)
2 int upperBoundSquareRoot = (int) Math.sqrt(upperBound);
3 /*这里取平方是因为通过数学推理可以知道只需要判断到upperBound的上界即可。
4 第一次写的读者可以把循环的次数设置成upperBound，便于理解*/
5 boolean[] isComposite = new boolean[upperBound + 1];
6 //这个boolean类型的数组是为了标记upperBound以内的自然数
7
8 for (int m = 2; m <= upperBoundSquareRoot; m++)
9 if (!isComposite[m])
10 System.out.print(m + " ");
11 for (int k = m * m; k <= upperBound; k += m)
12 isComposite[k] = true;
13
14
15 for (int m = upperBoundSquareRoot; m <= upperBound; m++)
16 if (!isComposite[m])
17 System.out.print(m + " ")；
18
参考文献：
1.Peter J. Giblin. Primes and Programming.
2.Hans Riesel. Prime Numbers and Computer Methods for Factorization.
素数筛法
一、埃式筛法 埃式筛法的核心思想是从2到n枚举，当我们找到一个质数时，枚举它所有的倍数，因为这些倍数都不可能是质数。for(inti=2;i<=n;i++){if(!vis[i]){prime[++cnt]=i;for(intj=i*2;j<=n;j+=i)vis[j]=true;}}时间复杂度是O(nloglogn)如果... 查看详情
埃氏筛法
/*2|埃式筛法|3|快速筛选素数| |15-7-26|4*/#include<iostream>#include<cstdio>usingnamespacestd;constintSIZE=1e7;intprime[SIZE];//第i个素数boolis_prime[SIZE];//true表示i是素数intslove(intn){intp=0;for(inti=0 查看详情
线性筛法求素数(代码片段)
...算法肯定挂（这也是自己被大佬们疯狂吊打的原因吧）。埃式筛第一种算法的时间复杂度太高了，下面介绍一种真正的筛法，即埃式筛，而且时间复杂度还比上面介绍的低（这不废话吗，比上面的高那还用介绍吗？）：#include<... 查看详情
hdu3823埃式筛法打表
...，使得a+x=c,b+x=d,c和d是质数并且相邻。解法：打素数表（埃式筛法）不成立：(b-a)&1或b==a成立：特殊：a=1,b=2,ans=1;a=2,b=3,ans=0;(c!=a,d!=b,b-a=d-c)&&b<=d, ans=d-b;#include<iostream>#include<cstdio>#include<cstring>#include<alg... 查看详情
埃氏筛法&欧拉筛法(代码片段)
埃氏筛法/*|埃式筛法||快速筛选素数| |15-7-26|*/#include<iostream>#include<cstdio>usingnamespacestd;constintSIZE=1e7;intprime[SIZE];//第i个素数boolis_prime[SIZE];//true表示i是素数intslove(intn)intp=0;for(inti=0;i<=n;i++)is_prime[i]=true;//初始化is_pr... 查看详情
初等数论-base-1(筛法求素数，欧拉函数，欧几里得算法)(代码片段)
...才开始了这篇博客.$P.S.$可能会分部分发表。筛法求素数埃式筛素数问题：求$[1,n]$中的所有素数总体思路就是在$[2,n]$中每当我们找到一个新的素数，在把它加入我们的素数队列的同时我们把它的倍数全部打上标记（包括它自己）... 查看详情
pat乙级1013.数素数(代码片段)
1013 数素数(20)（20 分）令P~i~表示第i个素数。现任给两个正整数M<=N<=10^4^，请输出P~M~到P~N~的所有素数。输入格式：输入在一行中给出M和N，其间以空格分隔。输出格式：输出从P~M~到P~N~的所有素数，每10个数字占1行，... 查看详情
pat-乙级-1013数素数(代码片段)
令 P?i?? 表示第 i 个素数。现任给两个正整数 M≤N≤10?4??，请输出 P?M?? 到 P?N?? 的所有素数。输入格式：输入在一行中给出 M 和 N，其间以空格分隔。输出格式：输出从 P?M?? 到&n... 查看详情
数论基础学习总结（持续补充中）(代码片段)
...^a_n|p_1<p_2<...<p_n,a_iinZ$上式中$p_i$为素数有关素数筛埃式筛法就是拿一个已经筛选出的素数去排掉其他的数，比如2是素数，就用他筛掉2*2，2*3，2*4&helli 查看详情
pat乙级1013(代码片段)
...题没把范围看清楚，没一次AC 题中m和n都表示第几个素数，范围是10000，所以查询的数组中需要的素数量至少10000，所以需要计算大概2~120000的整数才能查到10000个素数#include<iostream>#include<cmath>#include<vector>usingnamesp... 查看详情
素数的筛法(代码片段)
一写在开头1.1本文内容本文实现了素数的筛法算法。 二算法原理与实现在写代码的过程中，时不时会遇到求解素数的任务，特意将素数求解方法总结成文章以备不时之需。素数的求解算法大概有两种。一种是枚举某一范围的... 查看详情
pat乙级1013(代码片段)
1013数素数(20分)题目地址：https://pintia.cn/problem-sets/994805260223102976/problems/994805309963354112令(P_i)表示第i个素数。现任给两个正整数M≤N≤(10^4)，请输出(P_M)到(P_N)的所有素数。输入格式：输入在一行中给出M和N，其间以空格分隔。输出... 查看详情
蓝桥杯真题找素数(代码片段)
...lassMainpublicstaticvoidmain(String[]args)/*思路：暴力搜索+埃式筛选法先用一个函数生成[1,n]（n很大，比如n=10^8）范围的素数表，然后从1开始循环遍历该素数表直到第100002个素数。生成素数表可以用埃式筛选法&#... 查看详情
蓝桥杯中常用的数学算法(代码片段)
...数基本定义质数试除法$O(\\sqrtn)$朴素筛法求质数$(nlog_n)$埃式筛法$O(nlog_log_n)$~$O(n)$线性筛法$O(n)$约数试除法求约数$O(\\sqrtn)$求约数个数$O(\\sqrtn)$求约数之和求最大公约数求最小公倍数欧拉函数算数基本定义任何一个合数都可以写... 查看详情
算法中常用的数学知识(代码片段)
...除法O(n)O(\\sqrtn)O(n)朴素筛法求质数(nlogn)(nlog_n)(nlogn)埃式筛法O(nloglogn)O(nlog_log_n)O(nloglogn)~O(n)O(n)O(n)线性筛法O(n)O(n)O(n)约数试除法求约数O(n)O(\\sqrtn)O(n)求约数个数O(n)O(\\sqrtn)O(n)求约数之和求最 查看详情
pat乙级1013.数素数(20)
1013.数素数(20)时间限制100ms内存限制65536kB代码长度限制8000B判题程序Standard作者CHEN,Yue令Pi表示第i个素数。现任给两个正整数M<=N<=104，请输出PM到PN的所有素数。输入格式：输入在一行中给出M和N，其间以空格分隔。输出格式：... 查看详情
题目1084:用筛法求之n内的素数(代码片段)
类型：有关素数的基础算法思路：埃氏筛选AC代码：#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintMAX_N=10000000;intprime[MAX_N];boolis_prime[MAX_N];intp;void 查看详情
pat（b）1013.数素数
代码：#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;intprime(intn){if(n==2||n==3)return1;if(n%6!=1&&n%6!=5)return0;for(inti=5;i*i 查看详情