题目

我们知道第一个质数是 22、第二个质数是 33、第三个质数是 55……

请你计算第 20192019 个质数是多少？

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 128M

解答

  • 暴力解法
#include <iostream>
using namespace std;
int isPrime(int num) {
    // 判断一个数字是不是质数，return 0代表不是质数， return 1 代表是质数
    for (int i = 2; i < num; i++) {
        // 循环中判断是否能被1或者它本身之外的数字整除，若能则不是质数，直接return 0
        if (num % i == 0) {
            return 0;
        }
    }
    // 循环结束都没发现能整除的其他数字，可以返回1
    return 1;
}
int main()
{
    int count = 0; // 定义计数器，默认为0
    int answer = 0;
    for (int i = 2; count != 2019; i++) { // 从2开始循环是因为2是第一个质数，不要从1开始循环
        if (isPrime(i) == 1) { // 若判断为是质数
            count++; // 计数器++；
            answer = i; // 迭代更新answer
        }
    }
    cout << answer << endl; // 输出答案
    return 0;
}
  • 优化解法
#include <iostream>
using namespace std;

int main() {
    int n = 2019; // 要计算的质数的位置
    int num = 3; // 初始为3，因为第一个质数是2
    int count = 1; // 已经找到了一个质数2，所以从1开始计数

    while (count < n) {
        num += 2; // 只需要判断奇数是否为质数
        bool isPrime = true; // 假设当前数是质数
        for (int i = 3; i <= sqrt(num); i += 2) {
            if (num % i == 0) {
                isPrime = false; // 如果能被整除，则不是质数
                break;
            }
        }
        if (isPrime) {
            count++; // 找到一个质数
        }
    }
    cout << num << endl; // 输出第2019个质数
    return 0;
}
  • 线性筛法（Linear Sieve）

线性筛法是一种求解质数的算法，可以在$O(n)$的时间复杂度内预处理出小于等于$n$的所有质数。

线性筛法的基本思想是从小到大遍历每个正整数，如果它是质数，就将它加入质数数组中，并用它来筛掉它的倍数。在遍历过程中，对于每个数只会被它的最小质因子筛去，因此每个合数只会被筛一次，从而保证了线性时间复杂度。

下面是线性筛法的伪代码：

primes = [] # 质数数组
is_prime = [True] * (n+1) # 标记是否为质数
for i in range(2, n+1):
    if is_prime[i]:
        primes.append(i) # 将i加入质数数组
    for j in range(len(primes)):
        if i * primes[j] > n:
            break
        is_prime[i * primes[j]] = False # 将i*primes[j]标记为非质数
        if i % primes[j] == 0:
            break # 如果i是primes[j]的倍数，就跳出循环

如果在内层循环中，$i$是$primes[j]$的倍数，就跳出循环，这是因为$i$已经被$primes[j]$的其他倍数筛过了，不需要重复筛。

例如，当$i$为$2 \times 3=6$时，在内层循环中，$i$会被$2$筛一次，被$3$筛一次，之后就不需要再被其他数筛了。因此，如果$i$是$primes[j]$的倍数，就可以跳出循环，不需要继续遍历$primes$数组中的其他质数。这样可以减少重复的筛选，提高算法的效率。

C++代码实现如下：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 20000; // 估计2019个质数的上限
vector<int> primes; // 存储质数
bool isPrime[MAXN]; // 标记是否为质数

int main() {
    fill(isPrime, isPrime+MAXN, true); // 初始化标记数组，全部设置为true

    for (int i=2; i<MAXN; i++) {
        if (isPrime[i]) { // i是质数
            primes.push_back(i); // 将i加入质数数组
            if (primes.size() == 2019) {
                cout << primes.back() << endl;
                break;
            }
        }
        for (int j=0; j<primes.size() && i*primes[j]<MAXN; j++) {
            isPrime[i*primes[j]] = false; // 将i*primes[j]标记为非质数
            if (i % primes[j] == 0) break; // 如果i是primes[j]的倍数，就跳出循环
        }
    }

    return 0;
}

可以看到，线性筛法的实现相对简单，但需要注意以下几点：

  1. 对于每个数只需要用它的最小质因子来筛去它的倍数，因此内层循环的终止条件为$i \times primes[j] > n$。
  2. 在内层循环中，如果$i$是$primes[j]$的倍数，就跳出循环，这是因为$i$已经被$primes[j]$的其他倍数筛过了，不需要重复筛。
  3. 在初始化标记数组时，除0和1外都初始化为True。