高级光能
对埃氏筛的预习 找人普及一下知识
高级天翼
一、 埃氏筛法
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
二、 具体思想：
给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去…。
三、 算法流程
排出从1~N的数列：1 2 3 4 5 6 7 8 9 10 11 12 ……
1不是素数，也不是合数，划去
2是素数，把N以内所有2的倍数划去
3是素数…… 重复划去过程直到sqrt(N)
四、 埃氏筛法的好处
（1）我们发现运用筛法找出一个区间内的质数，非常高效。
（2）运用筛法的思想，可以将程序代码简化。
这是我以前的讲义。
新手天翼
你学了埃式筛后会发现，这个比传统找质数的方法快，只要你不出错，他的速度只有你想不到，没有他做不到，快的很，是桶排序思维，但筛的是合数，留下的是质数，希望对你有帮助
王子逸在2020-05-07 18:28:50追加了内容
他常用于寻找质数
高级天翼
高级守护
中级天翼
-
埃式筛法：给定一个正整数n(n<=10^6)，问n以内有多少个素数？
做法：做法其实很简单，首先将2到n范围内的整数写下来，其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。再将表中所有的3的倍数划去……以此类推，如果表中剩余的最小的数是m，那么m就是素数。然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数，这样的时间复杂度是O(nloglogn)。
题解：如果要是按照一个一个判断是否是素数然后把ans+1，时间复杂度为O(n√n)，对于10^6的数据时间复杂度就是O(10^9)，必定会超时，但此时埃氏筛法的时间复杂度只有O(nloglogn)。
int prime[MAXN];//第i个素数
bool is_pri[MAXN+10];//is_pri[i]表示i是素数
//返回n以内素数的个数
int sieve(int n){
int p=0;
for(int i=0;i<=n;i++)is_pri[i]=true;
is_pri[0]=is_pri[1]=false;
for(int i=2;i<=n;i++){
if(is_pri[i]){
prime[++p]=i;
for(int j=2*i;j<=n;j+=i)is_pri[j]=false;
}
}
return p;
}
-
区间素数筛：给定两个正整数a、b(a<b<=10^12、b-a<=10^6)，请问[a,b)内有多少个素数？
主要思想：既然在之前已经讲过b以内的和书的最小质因数不会超过√b。如果有√b以内的素数表的话，就可以把埃氏筛法运用在上面了。也就是说，我们可以先分别做好[2,√b)的表和[a,b)然后在第一个表的是素数的前提下，删去第二个表中的数即可。
#include<iostream> using namespace std; bool pri[1000000+10]; bool ispri[10000000+10];//ispri[i-a]=true代表i是素数 void getpri(){ memset(pri,true,sizeof(pri)); pri[0]=pri[1]=0; for(int i=2;i<=1000000;i++){ if(pri[i]){ for(int j=2*i;j<=1000000;j+=i)pri[j]=0; } } } int main(){ long long a,b; scanf("%lld%lld",&a,&b); getpri(); memset(ispri,true,sizeof(ispri)); for(long long i=2;i*i<b;i++){ if(pri[i]){ for(long long j=max((a+i-1)/i,2LL)*i;j<b;j+=i) ispri[j-a]=0; } } long long cnt=0; for(int i=0;i<b-a;i++)if(ispri[i])cnt++; if(a==1)cnt--; printf("%lld\n",cnt); }
武建豪在2020-05-07 22:19:54追加了内容
求采纳(っ °Д °;)っ
初级天翼
埃氏筛就是一种找质数的算法
中级光能
中级天翼
中级天翼
高级光能
埃拉托斯特尼筛法，简称埃氏晒，是一种用来求自然数n以内的全部素数。
他的基本原理是，如果我们要获得小于n的所有素数，那就把不大于根号n的所有素数的倍数剔除。
埃氏晒的原理很容易理解，一个合数，必然可以表示成，一个自然数 i 和一个素数的乘积。因此我们找到一个素数后，把他小于n的倍数全部标记为合数，这就是我们要做的。
void prime(int n) {
bool flag[MAX];//0为素数 1为合数
memset(flag, 0, sizeof(flag));
for (int i = 2; i * i < n; i++) {
//i为素数
if (flag[i] == false) {
for (int j = i * i; j < n; j += i) {
//将其倍数标记为合数
flag[j] = true;
}
}
}
}
上述代码有几个关键点要注意
1. 外层循环的终止条件是 i * i < n，因为我们是要把不大于根号n的所有素数的倍数剔除。
2. 内层循环，j 可以从 i * i 开始，因为 i * (2 ~ i –1 )，在之前的循环中，已经被筛去。
我们如果观察被筛掉的数据，我们可以发现，一个合数，可能会被筛掉多次，例如，
30 = 2 * 15 = 3 * 10 = 5 * 6，所以30 就至少被2，3，5这三个质数分别筛过了，这个地方就会造成时间的浪费。我们能不能找到一种关系，使得每个合数，只被筛掉一次呢？
线性筛(欧拉筛)
欧拉筛是一种复杂度很低的素数筛选法，原因在于，每一个合数，只被筛选了一次。
void euler_sieve(int n) {
//记录当前找到素数的数量
int sum = 0;
//flag用来记录第i个数字是否为合数 true为合数
bool flag[MAX];
memset(flag, 0, sizeof(flag));
//primes用来记录每一个找到的素数
int primes[MAX];
memset(primes, 0, sizeof(primes));
for (int i = 2; i <= n; i++) {
if (!flag[i])
primes[sum++] = i;
for (int j = 0; i * primes[j] <= n; j++) {
flag[i * primes[j]] = true;
if (i % primes[j] == 0)
break;
}
}
}
我们要用到的重要的定理：
n=Factorymax∗Pn=Factorymax∗P
上式中，n是一个合数，每一个合数都可以唯一的表示成如上的形式。其中
Factory是除了n以外的n的最大因数，而P满足一下两点：
1. P是一个素数
2. P小于等于Factory的所有因数
综上可知，P就是n的最小质因数。
证明如下：
1.假设P为合数，则P = P1 * P2 * ···· * Pn，其中，P1<P2<····<Pn，且Pi都为质数
因此存在一个F = Fatory * P1为n的因数，且F > Fatory，
所以和Factory是n的最大的因数矛盾，故假设不成立
2.假设P大于Factory的某个因数，不妨设P>P1
因为 Factory = P1 * P2 * ···· * Pn
因此 P * P2 * ··· * Pn 必然大于Factory
所以和Factory是n的最大因数矛盾，故假设不成立
上面的定理就是欧拉筛的原理，我们创建一个数组prime[]来存储目前找到的素数，一个数组flag[]用来标记数字是否为合数(合数为1)。我们每次枚举一个数字i(从2开始枚举)，如果这个flag[i] == 0，则i为质数，存入prime。然后把由i和目前已找到的素数相乘得到的合数，标记为1(flag[ i * prime[n]] = 1)。
如何保证prime[n]是i * prime[n] 的最小质因数？
由于任一个数字，都可以表示成有限质数的和，所以当 i % prime[n] == 0，时，可以得出，prime[n]是 i 的一个质因数，同时也是i * prime[n]的质因数，而prime[]数组中的素数，是我们从小到大得出的，此时prime[n]是 i * prime[n]的最小质因数(这部分不容易理解)，因此，prime[n+1] 等等都必定不是i * prime[n + 1]的最小质因数。
简单举个例子：
i = 77 = 7 * 11，此时prime[]中已经储存了 3 5 7 9 …等素数
1. prime[1] = 3 ，3满足 i * 3的最小质因数的条件
2.prime[2] = 5，5满足i * 5的最小质因数条件
3.prime[3] = 7，7满足 i * 7的最小质因数条件，但此时 i % 7 == 0，因为 i 的一个质因数也是7
4.prime[4] = 11，此时就不满足 是最小质因数的条件了，i 中有比11更小的因数，因此 i * 11 中也有比11更小的因数。
欧拉筛解释思路借鉴 链接
