线性筛——质数筛，莫比乌斯筛
质数筛
暴力版：
1 bool prime(int n) 2 { 3 for(int i=2;i<=sqrt(n);i++) 4 if(n%i==0) return false; 5 6 return true; 7 }
如果给定区间1到n，判断每一个数是不是质数，每个数都要从2开始暴搜，就某得灵魂。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。普通筛：
bool isprime[maxn];//1代表是质数，0代表不是 void judge() { memset(isprime,true,sizeof(isprime))//默认全都是质数 for(int i=2;i<=maxn;i++) { if(isprime(i)){//i是质数 for(int j=2;j*i<=maxn;j++)//那么i乘一个数就不是质数了 isprime[j]=0; } } }
这样就是一个线性的过程，从2开始到n筛，灵魂注入了一点，但弊端还是有，很多数被重复判断了。
真•线性筛（欧拉筛）：
bool isprime[n];//1代表是质数，0代表不是 int prime[n];//素数数组，从小到大装着1到n的素数 void judge() { memset(isprime,true,sizeof(isprime))//默认全都是质数 int tot=0 for(int i=2;i<=n;i++) { if(isprime(i))//是质数 prime[tot++]=i;//存到素数数组里
for(int j=0;j<tot&&prime[j]*i<n;j++) { isprime[ i * prime[j] ]=false; if(i%prime[j]==0)//保证每个合数都被它的最小素数筛掉 break; } } }
这个的思想和普通筛一样，但却避免了一个合数被多次判断。
慢慢来，首先i无论是不是素数，i乘一个prime[j]肯定就不是素数，如何避免重复筛呢，首先合数是一定有质因子的（合数能分解质因数），所以要找到j的界限，保证一个合数只被判断一次，线性筛是从小到大的，自然是找每个合数的最小质因子了。
结论：如果 i 能整除 prime[j] ，此时j就不能++了， i *prime[j+1] 肯定会被 prime[ j]乘某个数筛掉；
证明：i 若能整除 prime[ j]
则 i=k * prime[j]
则 i *prime[ j+1]=k*prime[ j ] *prime[j+1]
则 i * prime[ j + 1] = k' *prime[ j ]
所以每个合数都只会被它的最小质因数筛掉。
莫比乌斯筛
更多精彩
