代码之家 › 专栏 › 技术社区 › Thor

我的代码试图查找0到n之间的所有素数,在语句“bool prime[n+1];”中使用“+1”有什么用?

sieve-of-eratosthenes c++

2

Thor · 技术社区 · 10 年前

我是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;
}

2 回复 | 直到 9 年前

1

2

Abu Hanifa 10 年前

在里面 C++ 大小的数组 N 索引起始于 0 到 N-1 .所以对于你的问题,对于 N 索引分配 N+1 大小数组。从而定义了 N 数字

2

1

swinefish 10 年前

在C++(和许多其他语言)中,大小为n的数组具有0到(n-1)的索引。在这种情况下,您需要检查每个数字,包括n在内。因此,您需要在数组中的索引处为n指定一个点 prime[n] 。只有当数组超出1时,此索引才会存在。否则,数组将停止在 prime[n - 1] .

即使你把 - 1 C++对数组边界并不挑剔——一旦有了数组,就可以合法地读取或写入任何索引,无论该索引是否安全。注意,我说的是合法的,不是安全的——这是一种潜在的非常危险的行为。