1 #include<iostream>
 2 #define MAXN 1000010
 3 using namespace std;
 4 long prime[MAXN],number_prime;　　//prime 为素数的集合，number_prime 为素数的个数
 5 bool vis[MAXN];　　//vis 用于记录那些数不是素数
 6 inline void pd_prime(int number)　　//number 是所求素数集合的上限
 7 {
 8     for(int i=2;i<=number;i++)
 9     {
10         if(!vis[i]) prime[number_prime++]=i;　　//如果不在 非素数集合内 判定为素数--同时 number+1 （此时是number先赋值再+1，故prime序列从0开始）
11         for(int j=0;j<number_prime && i*prime[j]<=number;j++)　　//j要小于现在求出来的素数个数，并且下一步筛出的那个数（i*某已知素数要小于要求的上限）
12         {
13             vis[i*prime[j]]=true;　　//能拆成 i*质数 为合数 筛出
14             if(!(i%prime[j])) break;　　//见注解1 i%prime[j]==0
15         }
16     }
17 }
18 int main()
19 {
20     int n;
21     cin>>n;
22     pd_prime(n);
23     for(int i=0;i<number_prime;i++) cout<<prime[i]<<endl;
24     cout<<endl<<"total number: "<<number_prime;
25     return 0;
26 }