埃式筛

这是一个和辗转相除法一样古老的算法。原理也很简单。
首先将2到n范国内的整数写下来。其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数宇就是3，他不能被更小的数整除，所以3是素数。
再将表中所有的3的倍数划去
⋯以此类推，_ 如果表中剩余的最小的数是m，那么m就是素数。
然后将表中所有m的倍数划去，像这样反复操作。就能依次枚举n以内的素数

1.求1-20之间的素数个数

int main(){
    int cnt=0;//用来计数
    
    bool isprime[21];
    for(int i=0;i<=20;i++)isprime[i]=true;//先全部置为真
 
    isprime[0]=isprime[1]=false;//1 0 不是素数
 
    for(int i=2;i<=20;i++){//从2开始往后筛
        if(isprime[i]){
            for(int j=2*i;j<=20;j+=i){
                isprime[j]=false;
            }
        }
        if(isprime[i]){
            cnt++;//如果是素数 就计数
        }
    }
    printf("%d",cnt);
}