素数筛

判断某个整数n是否为素数,或者说求某个范围内的素数个数等等,这些是用到素数筛的最最基础的问题。

判断一个整数n是否为素数

首先i从2开始枚举到 \(\sqrt{n}\) ,然后一旦n可以被i整除,就返回false,然后如果i枚举完了,n都没能整除i,那就证明是素数,返回true。

bool isprime(int n){   //判断单个数n是否为素数
	if(n <= 1) return 0;
	for(int i=2;i*i<=n;i++)
		if(n % i == 0) return 0;
	return 1;
}

埃氏筛法

作用就是枚举n以内的素数

首先将2到n范围内所有的整数写下来,在这其中最小的数字2是素数,将表中所有2的倍数都划去,表中剩余最小的数字是3,它的因数只有它自己,(它已经最小了),然后就再把表中所有3的倍数都划去,以此类推,每次表中剩余的最小数字是m,m就是素数,然后将表中所有m的倍数都划去,这样反复操作之后就能依次枚举n以内的素数。

模板(数字n的作用就是筛出从1-n的素数,prime数组存这些素数,isprime[ i ]如果为1,则i是素数):

int prime[n],isprime[n];

int eratosthenes(int n){
	int p = 0;
	for(int i=0;i<=n;i++)
		isprime[i] = 1;//先假设这些数都是素数,后面再由它们的因数来划掉。
	isprime[0] = isprime[1] = 0;
	for(int i=2;i<=n;i++){
		if(isprime[i]){
			prime[p++] = i;
			for(int j = 2 * i;j <= n;j += i)
				isprime[j] = 0;
		}
	}
	return p;
}

埃氏筛法有一个缺陷,每次都要去对当前表内的素数m的所有的倍数进行删掉,也就是“visit[ j ] = 0” 这个操作,对于一个合数,它很有可能会被很多个素数筛到,也就重复进行了很多次操作,在此基础之上再次进行改进,我们还有欧拉筛法:


欧拉筛法

欧拉筛法并不是用目前最小素数的所有倍数来筛合数,而是要筛去一个合数时,用这个合数的最小质因子来筛去它。

欧拉筛法建立了一个数组prime,然后它的下标从1开始依次存的是这个区间的从小到大的素数,然后在外层循环for中让i累加,这里的i其实就是“倍数”的含义,然后循环的时候,取出数组中所有数,然后从小到大地对于i * 这些合数得到的值筛掉(它们都是合数)然后呢,i一直在增加,每一次执行这个筛操作之前,我们都要先判断一下i是否为素数,若是的话就把i加入前面的数组prime之中。

在这个筛操作中,还有一个跳出条件需要注意:if (i % prime[j] == 0) break;

这里跳出循环的意思是:当i是prime[ j ]的倍数时,i = k * prime[ j ] 如果进行下次循环,j 会加一指到prime数组中的下一个素数,下一次循环中 会出现 i * prime[ j+1 ] 而因为i是prime[ j ] 的倍数,所以上式变为 prime[j] * k * prime[j+1] ,这个表示的是一个合数,而这个合数的最小素因子其实是prime[ j ] ,而不是 prime[j+1] 。也就是说这个时候要筛掉的这个数在前面已经被筛掉了,因为它有一个更小的素因子,所以这已经是一次重复的筛运算了。然后接下来的j递增的内层循环中,i 一直是不变的,所以后面所有的i * prime[ j ] 都是会重复的,故至此跳出循环。接下来就进行下一次i的循环了。

下面prime[0] 表示有多少个素数,然后从数组的下标1开始存第一个素数,以此类推

代码:

const int maxn = 100;
int prime[maxn];
int vis[maxn];
void eularsieve(){
	memset(vis,0,maxn * sizeof(int));//是0表示i是素数
	memset(prime,0,maxn * sizeof(int));
	for(int i=2;i<maxn;i++){
		if(!vis[i])
			prime[++prime[0]] = i;
		for(int j=1;j <= prime[0] && i * prime[j] <= maxn;j++){
			vis[i*prime[j]] = 1;
			if(i % prime[j] == 0)
				break;
		}
	}
}

素数筛

上一篇:Dance with a stick 题解(思维)


下一篇:05.表达式目录树Expression