judge-prime-algorithm

判断素数

1.常规方法

ll isPrime(ll i) {
    ll ret = 1;
    if (i == 2) {
        return 1;
    } else if (1 == i || i % 2 == 0)
        return 0;
    ll k;
    for (k = 3; k * k <= i + 1; k += 2) {
        if (i % k == 0) {
            ret = 0;
            break;
        }
    }
    return ret;
}

比较简单，主要是进行了偶数筛除和折半优化。但正常方法一次只能判断一个数字的质数与否，如果想要找出一定范围的所有素数，就需要用到下面两种方法。

2.埃氏筛

埃氏筛的思想是：要想得到 n 以内的质数，就要把不大于 $\sqrt{n}$的质数的倍数全部剔除，剩下的就是质数。从 2 开始，把 2 的倍数（不包括本身）标记为合数，然后向后枚举，查到一个未标记为合数的，就把它的倍数（不包括本身）标记为合数。以此类推，查到 n 为止。
有一个小优化，把 t 的倍数标记为合数时，不是从 2t 开始，而是从$ t{^2} $开始（因为小于$ t{^2} $的 t 的倍数在枚举到 t 前就被标记过了）。

void Eratostheni_isprime(int n) {
    book[1] = 1;
    prime.push_back(2);
    for (int i = 3; i <= n; i += 2) {
        if (!book[i]) {
            prime.push_back(i);
        }
        for (int j = i; i * j <= n; j++) {
            book[i * j] = 1;
        }
    }
}

当然埃氏筛有个明显的缺点，就是会使结果被多次筛出，所以欧拉筛应运而生。

3.欧拉筛

避免重复筛，应找到筛合数的一种原则：这个合数只会被它的最大非自身因数（对应最小质因数）筛。这样能保证每个合数只会被筛一次。

void Euler_isprime(int n) {
    book[1] = 1;
    prime.push_back(2);
    for (int i = 3; i <= n; i += 2) {
        if (!book[i]) {
            prime.push_back(i);
        }
        for (int j = 0; j < prime.size() && i * prime[j] <= n; j++) {
            book[i * prime[j]] = 1;
            if (!(i % prime[j]))
                break;
        }
    }
}

欧拉筛的时间复杂度为O(n)，可以说使非常高效了。

模板题

【模板】线性筛素数

【模板】线性筛素数

题目背景

本题已更新，从判断素数改为了查询第 $k$ 小的素数
提示：如果你使用 cin 来读入，建议使用 std::ios::sync_with_stdio(0) 来加速。

题目描述

如题，给定一个范围 $n$，有 $q$ 个询问，每次输出第 $k$ 小的素数。

输入格式

第一行包含两个正整数 $n,q$，分别表示查询的范围和查询的个数。

接下来 $q$ 行每行一个正整数 $k$，表示查询第 $k$ 小的素数。

输出格式

输出 $q$ 行，每行一个正整数表示答案。

样例 #1

样例输入 #1

100 5
1
2
3
4
5

样例输出 #1

2
3
5
7
11

提示

【数据范围】
对于 $100%$ 的数据，$n = 10^8$，$1 \le q \le 10^6$，保证查询的素数不大于 $n$。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
bool book[M];
vector<int> prime;
int n, q;
void Euler_isprime(int n) {
    book[1] = 1;
    prime.push_back(2);
    for (int i = 3; i <= n; i += 2) {
        if (!book[i]) {
            prime.push_back(i);
        }
        for (int j = 0; j < prime.size() && i * prime[j] <= n; j++) {
            book[i * prime[j]] = 1;
            if (!(i % prime[j]))
                break;
        }
    }
}
void query(int k) {
    cout << prime[k - 1] << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> q;
    Euler_isprime(n);
    int k;
    while (q--) {
        cin >> k;
        query(k);
    }
    return 0;
}