如何解决查找第10001个质数时程序崩溃的问题？

嘿，我来帮你搞定这个问题！你遇到的崩溃大概率是内存访问越界或者静态数组大小不足导致的，毕竟找第10001个质数需要存储上千个质数，如果用了固定长度的数组，很容易在超过某个数量后溢出内存。改int为long解决不了这个核心问题，咱们一步步来解决：

• 静态数组容量不足：如果你一开始声明了一个固定大小的数组（比如int primes[3000];）来存储找到的质数，当找到的质数数量超过数组长度时，就会越界写入内存，直接触发崩溃。栈上的数组空间本来就有限，这种情况尤其常见。
• 算法效率过低导致假死：如果用的是最原始的暴力判断（比如对每个数都从2遍历到它本身），当数越来越大时，计算量会爆炸式增长，看起来像是程序崩溃，但其实是在疯狂计算没响应。不过你说的是明确崩溃，所以更可能是内存问题。
• 局部变量溢出：虽然把存储质数的变量改成了long，但如果循环计数器、平方根计算等中间变量还是用int，当数值超过int的最大值（2^31-1）时，会出现溢出，导致逻辑错误进而崩溃。

1. 换成动态扩容的存储结构 #

别用固定大小的数组了，改用动态数据结构，比如：

• C++里的std::vector
• Java里的ArrayList
• Python里的list
  这些结构会自动扩容，完全不用担心存不下质数。

2. 优化质数判断算法 #

判断一个数是否为质数时，不用遍历所有小于它的数，只需要做到两点：

• 只检查到这个数的平方根（如果一个数n有大于√n的因数，那对应的另一个因数肯定小于√n）
• 只除以已经找到的质数（因为合数的因数里一定包含质数）
  另外，除了2之外，所有质数都是奇数，所以可以跳过偶数，直接从3开始每次加2，减少一半计算量。

3. 示例代码（C++） #

#include <iostream>
#include <vector>
#include <cmath>

// 用已找到的质数来判断当前数是否为质数
bool isPrime(long long num, const std::vector<long long>& primes) {
    if (num < 2) return false;
    long long sqrtNum = sqrt(num);
    for (long long p : primes) {
        if (p > sqrtNum) break; // 超过平方根就不用再检查了
        if (num % p == 0) return false;
    }
    return true;
}

int main() {
    std::vector<long long> primes;
    primes.push_back(2); // 第一个质数是2
    int count = 1;
    long long num = 3;

    while (count < 10001) {
        if (isPrime(num, primes)) {
            primes.push_back(num);
            count++;
        }
        num += 2; // 跳过偶数，只检查奇数
    }

    std::cout << "第10001个质数是：" << primes.back() << std::endl;
    return 0;
}

4. 示例代码（Python） #

Python的动态列表天生适合这个场景，代码更简洁：

def is_prime(num, primes):
    if num < 2:
        return False
    sqrt_num = int(num ** 0.5)
    for p in primes:
        if p > sqrt_num:
            break
        if num % p == 0:
            return False
    return True

primes = [2]
count = 1
num = 3

while count < 10001:
    if is_prime(num, primes):
        primes.append(num)
        count += 1
    num += 2

print("第10001个质数是：", primes[-1])

如果还是不确定崩溃原因，可以用调试工具定位：

• Windows下用Visual Studio的调试模式，看崩溃时的调用栈和内存状态
• Linux下用gdb调试，查看是否是数组越界访问导致的段错误

这样修改后，程序不仅不会崩溃，运行速度也会快很多，很快就能算出第10001个质数（答案是104743，提前给你个参考）。

内容的提问来源于stack exchange，提问作者Silenc3