素数筛

模板

Primel1是常用的素数筛模板，Primer2能在线性时间筛选出素数。
n是素数的范围，p数组保存的是素数。

#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 25600000;
bool a[N];
int p[N];
int n;

void Prime1() {
    memset(a, 0, n * sizeof a[0]);
    int num = 0, i, j;
    for(i = 2; i < n; ++i) if(!a[i]) {
        p[num++] = i;
        for(j = i+i; j < n; j +=i) {
            a[j] = 1;
        }
    }

}

void Prime2() {
    memset(a, 0, n*sizeof a[0]);
    int num = 0, i, j;
    for(i = 2; i < n; ++i) {
        if(!(a[i])) p[num++] = i;
        for(j = 0; (j<num && i*p[j]<n); ++j) {
            a[i*p[j]] = 1;
            if(!(i%p[j])) break;
        }
    }
}
int main(){
    n = 100;
    Prime2();
}