c++ - 我昨天读到了埃拉托色尼筛法，想实现它

Question

我正在寻找有关算法实现的一些反馈。我该如何改进它？由于整数溢出，我在计算大于 46349 的较大素数时遇到了问题，但通过使用 sqrt 而不是 pow 解决了这个问题。

#include<iostream>
#include<math.h>
using namespace std;

int main(){
    int number;
    cin >> number;
    const int CAP = number;
    bool * prime = new bool[CAP];

    for(int i = 0; i <= CAP; i++){ //sets all to true for the marking
        prime[i] = true;
    }

    for(int i = 2; i <= number; i++){
        if(i <= sqrt(number) && prime[i] == true){
            for(int j = i*i; j <=number; j++){ //if %i == 0 mark false
                if(j % i == 0){               //haven't tried another way
                    prime[j] = false;
                }
            }
        }
    }

    for(int i = 2; i <= number; i++){
        if(prime[i] == true){
            cout << i << endl;
        }
    }

    return 0;
}

Answer 1

您正在越界访问数组:

bool * prime = new bool[CAP];

for(int i = 0; i <= CAP; i++)

您应该将其更改为使用 <而不是 <=

请注意，这同样适用于 <=在你的其他循环中也是如此。