基础模板/算法

线性筛求素数

#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;
}