素数筛（埃氏筛法）

CR__7 · 2021-08-28 14:23:20 · 个人记录

问题一：求1-20之间的素数的个数

#include<iostream>
#include<cstdio>

using namespace std;
bool isprime[21];
int cnt;
int main()
{
    for(int i=0;i<=20;i++)
        isprime[i]=1;//先全部设置为真 

    isprime[0]=isprime[1]=0;//0和1不是质数 

    for(int i=2;i<=20;i++)//从2开始往后筛 
    {
        if(isprime[i])
            for(int j=i*2;j<=20;j+=i)
                isprime[j]=0;
        if(isprime[i])
            cnt++;//如果是素数就加一 
    }
    cout<<cnt;
    return 0;
}

问题二：区间素数的个数

#include<stdio.h>
#include<algorithm>
#include<math.h>
const int maxn=1e6+7;//总的范围规定在这里
using namespace std;

//我们将这个埃氏筛法写成一个函数
bool isprime[maxn];
void sieve(){
    for(int i=0;i<=maxn;i++)isprime[i]=true;
    isprime[0]=isprime[1]=false;
    for(int i=2;i<=maxn;i++){//从2开始往后筛
        if(isprime[i]){
            for(int j=2*i;j<=maxn;j+=i){
                isprime[j]=false;
            }
        }
    }
}

int l,r; 
int main(){
    //我们在程序刚开始 先调用这个函数
    //把这个isprime数组处理成我们想要的样子 用来判断素数
    //这就是预处理的思想 我们在开头处理这一次
    //把isprime数组 里面 下标是素数的全部变成了true
    //后边想判断是不是素数 直接用isprime[i]是不是真就好了
    sieve();

    int cnt=0;//计数
    scanf("%d%d",&l,&r);//输入 l和r
    for(int i=l;i<=r;i++){//遍历 l到r  判断就行了
        if(isprime[i]){
            cnt++;
        }
    }
    printf("%d",cnt);
}

问题三 输入一个数n 判断他是不是素数（多组测试数据）

#include<stdio.h>
#include<algorithm>
#include<math.h>
const int maxn=1e6+7;//总的范围规定在这里
using namespace std;

//我们将这个埃氏筛法写成一个函数
bool isprime[maxn];
void sieve(){
    for(int i=0;i<=maxn;i++)isprime[i]=true;
    isprime[0]=isprime[1]=false;
    for(int i=2;i<=maxn;i++){//从2开始往后筛
        if(isprime[i]){
            for(int j=2*i;j<=maxn;j+=i){
                isprime[j]=false;
            }
        }
    }
}

int n; 
int main(){
    sieve();//预处理

    //输入 n
    while(scanf("%d",&n)!=EOF){
        if(isprime[n]){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }
}