线性筛选求素数（质数）

原理：
首先要明白的是，如果一个数是素数，那么他的倍数也就不是素数（线性筛选法主要就是利用这个思想，快速的过滤掉一大部分数，以达到快速筛选的目的，减小时间复杂度），例如：3是一个素数，如果要求10以内的素数，那么在查到3是素数的同时，就会把6和9给排除掉。

#include <bits/stdc++.h>//万能头文件
using namespace std;
const long MAX = 1000000;
long prime[MAX]={0},k=0;//prime存素数
int NotPrime[MAX]={1,1};//判断是否不是素数，若i为素数，则NP[i]=0
long selectPrime(long max);//声明一个筛选素数的方法
int main(){
long n;
cin >> n;//输入一个数，求这个数以内的所有的素数
selectPrime(n);
return 0;

}
long selectPrime(long max){

for(long i=2;i<max;i++)
{
if(!NotPrime[i]) prime[k++]=i;//如果是素数就加入prime数组
for(long j=0;j<k&&i*prime[j]<max;j++)
{
NotPrime[i*prime[j]]=1;//之前的每个素数的i倍都不是素数
if(!(i%prime[j])) break;
//如果遇到i为合数，我们只认为合数由一个最小的素数*合数得到，也不会重复（就像12=2*6而不是12=3*4）
}
}
for(long i = 0; i < k; i++){//对存素数的数组进行遍历输出
cout << prime[i] << " ";
}
return 0;
}

线性筛选求素数（质数）

原文：https://www.cnblogs.com/haust-1003/p/14588130.html