埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

详细列出算法如下：

  1. 列出2以后的所有序列：

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  2. 标出序列中的第一个素数，也就是2，序列变成：

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  3. 将剩下序列中，划掉2的倍数，序列变成：

    2 3 5 7 9 11 13 15 17 19 21 23 25

  4. 如果现在这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。

  5. 本例中，因为25大于2的平方，我们返回第二步：

  6. 剩下的序列中第一个素数是3，将主序列中3的倍数划掉，主序列变成：

    2 3 5 7 11 13 17 19 23 25

  7. 我们得到的素数有：2，3

  8. 25仍然大于3的平方，所以我们还要返回第二步：

  9. 现在序列中第一个素数是5，同样将序列中5的倍数划掉，主序列成了：

    2 3 5 7 11 13 17 19 23

  10. 我们得到的素数有：2，3，5 。

  11. 因为23小于5的平方，跳出循环.

结论：2到25之间的素数是：2 3 5 7 11 13 17 19 23。

#include <bits/stdc++.h>
using namespace std;

const long long maxn = 10000007 + 10;
const long long maxp = 700000;
int vis[maxn];    // i是合数vis为1，i是素数，vis为0
long long prime[maxp];

void sieve(long long n){
    long long m = (long long)sqrt(n + 0.5);
    memset(vis, 0, sizeof(vis));
    vis[2] = 0;
    for (long long i = 3; i <= m; i += 2) {
        if(!vis[i])
            for (long long j = i * i; j <= n; j += i)
                vis[j] = 1;
        if(i * i > n)
            break;
    }
}

long long gen(long long n){
    sieve(n);
    long long c = 1;
    prime[0] = 2;
    for (long long i = 3; i <= n; i += 2)
        if(!vis[i])
            prime[c++] = i;
    return c;
}

int main()
{
    long long n, c;
    cout << "刷素数到n：";
    cin >> n;
    c = gen(n);
    for (long long i = 0; i < c; i++)
        printf("%lld", prime[i]);
    cout << endl << c;
    return 0;
}

问题一 求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);
}

问题二 素数个数问题

#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);
}