c++ - 两百万以下的素数之和。埃拉托色尼筛法

Question

在解决问题时遇到了一些麻烦:“计算 200 万以下素数之和”。我正在使用“Eratosthenes 筛法”方法。我的方法可以很好地找到直到 100 的素数，但是当我试图找到直到 2,000,000 的素数之和时，我得到了错误的答案。

#include <iostream>

using namespace std;
long long unsigned int number[2000008];
int x=2000000LLU;
int sum()
{
    int s=0LLU; //stores sum
    for(int y=2; y<=x; y++) //add all the numers in the array from 2 to 2 million
    {
        s+=number[y];
    }
    return s;
}

int main()
{
    int k=2;
    for(int i=2; i<=x; i++) //fills in numbers from 2 to 2 million in the array
    {
        number[i]=i;
    }
    for(int j=2; j<=x; j+=1) //starts eliminating multiples of prime numbers from the grid
    {
        if(number[j]!=0) //moves through the grid till it finds a number that hasnt been crossed out. ie. isnt zero                            
        {
            for(int y=j+j; y<=x; y+=j) //when it finds a number, it removes all subsequent multiples of it
            {
                number[y]=0;
            }
        }

    }  
    cout<<endl<<"done"; //shows that the loop has been completed
    cout<<sum(); //outputs the sum of the grid
    return 0;
}

Answer 1

我不确定 int 是否足以保存答案...它可能大于 32 位值。尝试在整个过程中使用 long long。