1 int prime[maxn];//第i个素数
 2 bool is_prime[maxn];//is_prime[i]为true表示i是素数
 3 int sieve(int n)//返回n以内的素数
 4 {
 5     int cnt=0;
 6     for(int i=0;i<=n;i++)
 7         is_prime[i]=true;
 8     is_prime[0]=is_prime[1]=false;
 9     for(int i=2;i<=n;i++)
10         if(is_prime[i])
11         {
12             prime[cnt++]=i;//边筛边记录素数
13             for(int j=2*i;j<=n;j+=i)
14                 is_prime[j]=false;
15         }
16     return cnt;
17 }

时间复杂度:O(nlog2n)

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。