线性筛求素数

#include<bits/stdc++.h>
using namespace std;

const int N = 5e7+50;

int n, tot, prime[N];  //prime存储所有素数
bool flag[N];   //判断是否为素数

int main(){

    scanf("%d", &n);
    
    //初始化，flag全部置为true
    for(int i=1; i<=n; i++) flag[i] = true;

    for(int i=2; i<=n; i++)
    {
        if(flag[i])   //如果i是素数就将其存储在prime
            prime[++tot] = i;
        
        /* 线性筛的核心
        每循环到一个i就将所有已知素数与它的乘积标记为不是素数 */
        for(int j=1; j<=tot; j++){
            if(prime[j]*i > n) break; //容易明白，因为最大是n
            flag[i*prime[j]] = false;
            if(i%prime[j] == 0) break;
            //i是某素数乘积，则i*任何数也是该素数乘积（那么肯定被判断过了）
            //两个判断都必须，不然会超时
        }
    }

    for(int i=1; i<=tot; i++){
        printf("%d\n",prime[i]);
    }
 
return 0;
}