使用埃氏筛法实现LeetCode计数质数问题时遇空指针运行时错误

错误信息 #

Line 86: Char 2: runtime error: store to null pointer of type 'std::_Bit_type' (aka 'unsigned long') (stl_bvector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_bvector.h:95:2..

你的代码 #

class Solution {
public:
    int countPrimes(int n)
    {
        int count = 0;

        vector<bool> prime(n, true);

        prime[0] = prime[1] = false;

        for (int i = 2; i < n; i++) {
            if (prime[i]) {
                count++;
                for (int j = i * 2; j < n; j = j + i) {
                    prime[j] = 0;
                }
            }
        }
        return count;
    }
};

错误原因 #

你的代码未处理n<=1的边界情况：

• 当n=0时，vector<bool> prime(n, true)的长度为0，此时访问prime[0]属于越界访问；
• 当n=1时，vector长度为1，仅存在索引0，访问prime[1]同样越界；
• vector<bool>是C++标准库的特化实现，底层用位存储，越界访问会触发空指针类型的运行时错误，也就是你看到的报错。

修正方案 #

在代码开头先处理边界情况，当n<=2时直接返回0（因为小于2的数没有质数），再执行后续筛法逻辑：

class Solution {
public:
    int countPrimes(int n)
    {
        if (n <= 2) return 0;
        int count = 0;

        vector<bool> prime(n, true);

        prime[0] = prime[1] = false;

        for (int i = 2; i < n; i++) {
            if (prime[i]) {
                count++;
                for (int j = i * 2; j < n; j += i) {
                    prime[j] = false;
                }
            }
        }
        return count;
    }
};

另外补充：你代码里用prime[j] = 0虽然能运行，但更规范的写法是prime[j] = false，因为vector<bool>存储的是布尔值。

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