筛质数

洛谷-P3383-【模板】线性筛素数

埃氏筛

原理

见《进阶指南》第135页。

代码

#include <iostream>
using namespace std;

const int N = 100000010;
int idx, primes[N];
bool mark[N];

void get_primes (int n) {
    for (int i = 2; i <= n; ++ i) {
        if (mark[i] == true) continue;
        primes[++ idx] = i;
        for (int j = i; j <= n / i; ++ j) mark[i * j] = true;
    }
}

int main () {
    int n, q;
    scanf("%d%d", &n, &q);

    get_primes(n);
    while (q --) {
        int k;
        scanf("%d", &k);
        printf("%d\n", primes[k]);
    }
    return 0;
}

线性筛

原理

见《进阶指南》第136页。

代码

#include <iostream>
using namespace std;

const int N = 100000010;
int idx, primes[N];
bool mark[N];

void get_primes (int n) {
    for (int i = 2; i <= n; ++ i) {
        if (mark[i] == false) primes[++ idx] = i;
        for (int j = 1; primes[j] <= n / i; ++ j) {
            mark[i * primes[j]] = true;
            if (i % primes[j] == 0) break; // primes[j] 一定是 i 的最小质因子
        }
    }
}

int main () {
    int n, q;
    scanf("%d%d", &n, &q);

    get_primes(n);
    while (q --) {
        int k;
        scanf("%d", &k);
        printf("%d\n", primes[k]);
    }
    return 0;
}