时间复杂度为O（n）的线性筛函数：

 

#include
      
       #include
       
        #include
        
         const int maxn=1e5+5;using namespace std;bool prime[maxn];int primes[maxn];int num_prime=0,n;void make_prime(){    memset(prime,true,sizeof(prime));    prime[0]=prime[1]=false;    for(int i=2;i<=n;i++){        if(prime[i]){            primes[num_prime++]=i;            printf("%d ",i);        }        for(int j=0;j
         
          <=n;j++){            prime[i*primes[j]]=false;            if(!(i%primes[j]))break;        }    }}int main(){    scanf("%d",&n);    make_prime();    return 0;}