我的代码试图找到 0 到第 n 个数之间的所有质数，语句 'bool prime[n + 1];' 中的“+ 1”有什么用？

Question

我是 C++ 的新手，正在尝试解决初学者的问题，即找到 0 到第 n 个数之间的所有素数。我在网上看到了这段代码，它运行得很好。

但是，我的问题是语句 'bool prime[n + 1];' 中的“+ 1”有什么用？我已将其从代码中删除，一切似乎都运行良好。有必要还是多余？

void SieveOfEratosthenes(int n) {

    bool prime[n + 1];
    memset(prime, true, sizeof (prime));



    for (int p = 2; p * p <= n; p++) {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
            // Update all multiples of p
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }

    // Print all prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            cout << p << endl;
}

int main() {
    int n = 1000;
    cout << "Following are the prime numbers smaller "
            << " than or equal to " << n << endl;
    SieveOfEratosthenes(n);
    return 0;
}

Answer 1

在 C++ 中，大小为 N 的数组的索引从 0 开始到 N-1。所以对于你的问题，为 N 索引分配 N+1 大小的数组。这样就可以将素数定义为 N number.

Answer 2

在 C++（和许多其他语言）中，大小为 n 的数组具有 0 到 (n - 1) 的索引。在这种情况下，您将需要检查每个数字，直到并包括 n。因此，您需要在数组中为 n 找一个位置，索引为 prime[n]。仅当数组超大 1 时，该索引才会存在。否则，数组将停止在 prime[n - 1]。

即使你去掉 - 1 也能工作的原因是 C++ 对数组边界不挑剔——一旦你有了一个数组，你就可以合法地在任何索引处读取或写入，无论该索引是否是安全的。请注意，我说的是合法的，而不是安全的——这可能是非常危险的行为。

我的代码试图找到 0 到第 n 个数之间的所有质数，语句 'bool prime[n + 1];' 中的“+ 1”有什么用？

My code is trying to finding all prime numbers between 0 - nth number, what is the use of '+ 1' within the statement 'bool prime[n + 1];'?

c++

sieve-of-eratosthenes