埃氏筛

埃拉托色尼筛法（Sieve of Eratosthenes）是古希腊数学家埃拉托色尼提出的一种高效算法，用于寻找小于等于某个给定数 ( n ) 的所有质数。其主要思想是通过标记合数的方法来筛选出质数。埃氏筛的时间复杂度为 ( O(n \log \log n) )，在处理大规模数据时非常高效。

#include<bits/stdc++.h>
using namespace std;
bool isprime[1000000];//默认是0,我们认为当是0的时候这个数是素数  
int prime[1000000];  
int cnt;//判断有多少个素数
int main()
{
    int a;
    cin >> a;
    for(int i = 2;i <= a;i ++)
    {
        if(!isprime[i])
            {
                prime[++cnt] = i;
                for(int j = 2;i *j <= a;j ++)
                {
                    isprime[j] = 1;
                } 
            }
     }
}

最后我们得到的prime数组中存放着素数是什么，cnt表示素数有多少个