筛选法求素数

基本原则：题目如果只需要判断少量数字是否为素数，直接枚举因子2……N^(0.5) ，看看能否整除N。
如果需要判断的次数较多，则先用下面介绍的办法预处理。

一般的线性筛法

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int Max=10000000;
bool primes[Max]={false};//假设全为质数
int prime[Max]={0};//假设在[0,n]的质数个数为0
void count_Prime(int n){
    primes[1]=true;
	prime[1]=1;//1为质数，在[0,1]内质数个数为1
	int i,j;
	for(i=2;i<=n;i++){
		prime[i]=prime[i-1];
		//[0,i-1]内的质数个数+第i个数是否为质数（是+1，不是+0）的总和为[0,i]内的质数个数
		if(primes[i]==false){//若第i个数为质数，则[0,i]内的质数个数+1
			prime[i]++;
			for(j=i*2;j<=n;j+=i)//筛选出质数的相关合数
				primes[j]=true;
		}
	}
}

初始时，假设全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数(注意上面的 ii , 比 i2 要快点 )，把这些合数都筛掉。
但仔细分析能发现，这种方法会造成重复筛除合数，影响效率。比如在i=2的时候，k=2X15筛了一次；在i=5，k=5X6 的时候又筛了一次。所以，也就有了快速线性筛法。

快速线性筛法