数学——数论--6倍数素数判别法

大于等于5的质数一定和6的倍数相邻。

证明：

将大于等于5的倍数表示出来，$x \geq 1$，$6x - 1, 6x, 6x + 1, 6x+2, 6x+3, 6x+4,6x+5, 6(x+1) \cdots$

• 首先$6x$肯定不是素数
• $6x + 2, 6x+4$一定是偶数，肯定不是素数
• $6x+3$显然是3的倍数

所以只有$6x+1, 6x+5$这种形式才**有可能**是素数，这就意味着我们可以把搜索的步长设置为6，效率明显提高。

• Project Euler 7-10001^st prime
• 【洛谷P3383】筛法求素数

题意大概就是多组测试数据，每行一个n，找出第n个素数。

#include <bits/stdc++.h>

using namespace std;

vector<long long> seq;

bool isPrime(long long n)
{
    long long limit = sqrt(n) + 1;
    for (long long i = 3; i <= limit; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

void calculate()
{
    long long number = 5;
    while (true) {
        if ((int)seq.size() >= 1e4) break;
        if (isPrime(number)) seq.push_back(number);
        if (isPrime(number + 2)) seq.push_back(number + 2);
        number += 6;
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    seq.push_back(2), seq.push_back(3);
    calculate();

    int caseNum; cin >> caseNum;
    int n;
    while (caseNum--) {
        cin >> n;
        cout << seq[n - 1] << endl;
    }

    return 0;
}

方法是采用预处理，用一个数组seq存储素数，因为数据范围为$10^4$，所以不会超过内存限制。这样预处理之后，每个查询是$O(1)$的时间复杂度。

分析一下预处理的时间复杂度，第$10^4$个素数是104729，在$10^5$级别，判定素数的时间复杂度是$O(\sqrt n)$，所以是$10^4 / 6 \times \sqrt{10^5}$，是$10^7$级别，一般评测机还是可以通过的。