- int prime[maxn];// 第 i 个素数
- bool is_prime[maxn];//is_prime[i] 为 true 表示 i 是素数
- int sieve(int n)// 返回 n 以内的素数
- {
- int cnt=0;
- for(int i=0;i<=n;i++)
- is_prime[i]=true;
- is_prime[0]=is_prime[1]=false;
- for(int i=2;i<=n;i++)
- if(is_prime[i])
- {
- prime[cnt++]=i;// 边筛边记录素数
- for(int j=2*i;j<=n;j+=i)
- is_prime[j]=false;
- }
- return cnt;
- }
时间复杂度: O(nlog2n)
来源: http://www.bubuko.com/infodetail-2997246.html