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(nlog_2ⁿ)