线性筛求素数
#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全部置为truefor(int i=1; i<=n; i++) flag[i] = true;for(int i=2; i<=n; i++){if(flag[i]) //如果i是素数就将其存储在primeprime[++tot] = i;/* 线性筛的核心每循环到一个i就将所有已知素数与它的乘积标记为不是素数 */for(int j=1; j<=tot; j++){if(prime[j]*i > n) break; //容易明白,因为最大是nflag[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;
}