质数:在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数
小于等于N大概有lgN个质数
质数的判定
试除法 判断一个数N:O(√N)
扫描2-√N之间所有整数,一次检查它们能否整除N
质数筛:求出小于等于n的所有质数,特判v[1]=1
i从小到大,如果i
没有被前面的数(比它小的数)标记为合数,那i
就是素数,加入素数列表
用已经筛选出来的素数去过滤所有能够被它整除的数
埃及筛 O(NloglogN)
扫描2-N,若这个数未被标记,则把它的倍数标记为合数
->会重复标记合数
void shai() {
v[1]=1; for(int i=2;i<=n;i++) if(v[i]) continue; for(int j=i;j*i<=n;j++) v[i*j]=1;//合数 }
欧拉筛 O(N)
用已经筛选出来的素数去过滤所有能够被它整除的数,使得每个合数只会被它的最小质因子筛一次(一开始i很小的时候一次能筛掉很多素数,后面超过n/2之后就几乎不用做什么事情了)
用当前的数×之前的筛出来的素数,这个数即为合数
void shai() { v[1]=1; cnt=0; for(int i=2;i<=maxn;i++) { if(!v[i]) prime[++cnt]=i; for(int j=1;j<=cnt&&i*prime[j]<=maxn;j++) { v[i*prime[j]]=1; if(i%prime[j]==0) break; } } }
莫名其妙的一步...
if(i%prime[j]==0) break;
设当前数为a=b*c
若b是a的最小质因数,c的最小质因数比不小于b,保证了c筛掉前a不会被筛掉
标签:标记,int,质数,23,素数,整除,合数 From: https://www.cnblogs.com/blogzy/p/18030386