判断某个整数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;
}
}
}