素数

不打表素数求法 10^5
int sqr=sqrt(n);

bool isprime(int n)
{
    if(n<=1) return false;
    int sqr=sqrt(n);
    for(int i=2;i<=sqr;i++)
    {
        if(n%i==0) return false;
    }
    return true;
}

打表写法(埃式)，素数个数cnt个，下标1-cnt 10^5 没问题

bool st[N];
int primes[N],cnt=0;
void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[++cnt]=i;
            for(int j=i+i;j<=n;j+=i)
                st[j]=true;
        }
    }
}

get_primes(maxp);