前言

我们不如叫它“6倍筛法” （笑

关于素数的6倍原理

只有6k-1和6k+1才“有可能”是质数

先列一段素数

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ……

我们关于6k列出附近的数：6k-3, 6k-2, 6k-1, 6k, 6k+1, 6k+2, 6k+3

先考虑6k-3, 6k-2, 6k+2, 6k+3

显然6k-3和6k+3可以整除3，另6k-2, 6k+2可以整除2

所以这些肯定不是素数

只有6k-1和6k+1才“有可能”是质数

6k±1如果有因子，只能是6m±1

反证法：

若 6k±1 的因子不是6m±1

则，只能是 6m±2 或 6m±3

若是6m±2，则有 奇数6k±1 = 偶数(6m±2)*n , 显然不成立

若是6m±3，则有 3*(2k)±1 = 3*(2m±1)*n , 显然也不成立

所以6k±1如果有因子，只能是6m±1

那么我们为什么不可以以此来进行筛法呢?

代码如下，本地自测比欧拉快一点，理论上也是比欧拉快

int pr[1000010]={2,2,3};
bool is_not_pr[MAXN];
void Sieve(int n){
    for(res k=5;k<=n;k+=6){
        bool flag=0;
        if(!is_not_pr[k]){
            pr[++pr[0]]=k;
            for(res i=5;i*k<=n;i+=6){
                is_not_pr[i*k]=1;
                if((i+2)*k<=n) is_not_pr[(i+2)*k]=1;
            }
            flag=1;
        }
        if(!is_not_pr[k+2]){
            pr[++pr[0]]=k+2;
            for(res i=5;i*(k+2)<=n;i+=6){
                is_not_pr[i*(k+2)]=1;
                if((i+2)*(k+2)<=n) is_not_pr[(i+2)*(k+2)]=1;
            }
            if(flag) printf("%d and %d\n",k,k+2);
        }
    }
}

进一步优化：

int pr[1000010]={2,2,3};
bool is_not_pr[MAXN];
void Sieve(int n){
    for(res k=5;k<=n;k+=6){//res ==> register int
        if(!is_not_pr[k]){
            pr[++pr[0]]=k;
        }
        if(!is_not_pr[k+2]){
            pr[++pr[0]]=k+2;
        }
        for(res i=1;pr[i]*k<=n&&i<=pr[0];++i){
            is_not_pr[pr[i]*k]=1;
            if(pr[i]*(k+2)>n) continue;
            is_not_pr[pr[i]*(k+2)]=1;
        }
    }
}