c++ - 为什么我的代码说 109 不是素数？

Question

我正在尝试生成素数，我几乎让它工作了，但出于某种原因，当 109 是素数时，它显示 109 不是素数。

因此，当我输出 factorCount 时，它显示“113::29”，因为 113 是第 30 个质因数，因为它是 107 而不是 109。

#include <iostream>

using namespace std;

void mark(bool arr[], int a, int n){
    int i = 2;
    int num = 0;

    while((num = i*a) <= n){
        arr[num-1] = 1;
        i++;
    }
}

void sieve(int n){

    int primeCount = 0;

    if(n >= 2){
        bool arr[n];

        for(int i=1; i<n; i++){
            if(arr[i] == 0){
                primeCount++;
                cout << i+1 << " :: " << primeCount << endl;

                mark(arr, i+1, n);
            }
        }
    }
}

int main(){

    int n = 120;

    sieve(n);

    return 0;
}

Answer 1

您的代码使用了未初始化的变量:

bool arr[n];

for(int i=1; i<n; i++){
    if(arr[i] == 0){      // <--- here

您检查 arr[i] 的值当你没有将它设置为任何东西时。

此外，bool arr[n];在 C++ 中是非法的，尽管一些编译器将其添加为扩展。在标准 C++ 中，数组边界必须在编译时已知。要修复它，请更改 bool arr[n];到:

std::vector<unsigned char> arr(n);  // note: parentheses, not square brackets

此版本将对成员进行零初始化。遗憾vector<bool>不会在这里工作，因为它有一个奇怪的特化。您需要通过 &arr[0]至 mark , 而不仅仅是 arr .