200 万以下的素数之和。埃拉托斯特尼筛法

Question

解决问题时遇到一点困难：“计算 200 万以下的素数之和”。我正在使用“埃拉托斯特尼筛法”。我的方法可以很好地查找 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。

Answer 2

通过有效地使用埃拉托斯特尼筛，我解决了这个问题，这是我的代码，它是高度优化的

public class SumOfPrime {

    static void findSum()
    {
        long i=3;
        long sum=0;
        int count=0;
        boolean[] array = new boolean[2000000];
        for(long j=0;j<array.length;j++)
        {
         if((j&1)==0)
          array[(int)j]=false;   
         else    
         array[(int)j]=true;
        }
        array[1]=false;
        array[2]=true;
        for(;i<2000000;i+=2)
        { 
            if(array[(int)i] & isPrime(i))
            {   
                array[(int)i]=true;
                //Sieve of Eratosthenes
                for(long j=i+i;j<array.length;j+=i)
                    array[(int)j]=false;
            }
        }
        for(int j=0;j<array.length;j++)
        {
            if(array[j])
            {   
             //System.out.println(j);
             count++;   
             sum+=j;
            }
        }   
        System.out.println("Sum="+sum +" Count="+count);
    }
    public static boolean isPrime(long num)
    {
        boolean flag=false;
        long i=3;
        long limit=(long)Math.sqrt(num);
        for(;i<limit && !(flag);i+=2)
        {
            if(num%i==0)
            {
                flag=false;
                break;
            }   
        }
        if(i>=limit)
         flag=true;
        return flag;
    }

    public static void main(String args[])
    {
        long start=System.currentTimeMillis();
        findSum();
        long end=System.currentTimeMillis();
        System.out.println("Time for execution="+(end-start)+"ms");
    }

}

输出是

Sum=142913828922 Count=148933
Time for execution=2360ms

如果您有疑问，请告诉

Answer 3

使用无符号 64 位整数计算 sum

@Omri Barel 的回答确定了OP代码中需要的最小修改：

尝试在全文中使用 long long。

这可行，但太过分了。仅必须使用 64 位变量计算总和。数组中的数字最好存储为 32 位数量。对于高达 200 万的值，不需要 64 位。使用 std::uint32_t 可以节省大量存储空间。

我的偏好是使用标头 中的类型别名。它们允许您说出您想要多少位。此外，我对所有下标都谨慎使用 std::size_t 类型。

如果您继续使用 OP 使用的“全局”变量，则会给出以下声明。 enum 用于创建编译时常量：

enum : std::uint32_t { x = 2'000'000u };
enum : std::size_t { array_size = static_cast<std::size_t>(x) + 1u };
std::uint32_t number[array_size];  // `x` is a valid subscript.

请参阅下面的消除全局变量的方法。

使用 std::accumulate 添加数字

如果您小心地将数组 number 的前两个元素清零，则可以使用 std::accumulate< /code> 计算总和。

• std::cbegin 和 std::cend 具有接受内置数组作为参数的重载。
• 第三个参数 std::uint64_t{} 强制 std::accumulate 使用无符号 64 位算术进行计算。

std::uint64_t sum()
{
    return std::accumulate(std::cbegin(number), std::cend(number), std::uint64_t{});
}

类型之间的转换

由于数组 number 的元素具有 std::uint32_t 类型，而其下标具有 std::size_t 类型，因此必须使用将下标分配给数组时进行强制转换。否则，您的编译器可能会发出警告，指出赋值涉及“缩小”值。

// Variable `i` is a subscript, of type `std::size_t`.
number[i] = static_cast<std::uint32_t>(i);

重新访问 OP 中的程序

这是 OP 中的完整程序，并进行了上述修改。您应该能够复制、编译和执行，而无需摆弄。

// main.cpp
// 
// A few limited fixes were made to the code below.
//   1. Change `number` type to array of `std::uint32_t`. 
//      Using `long long unsigned` for this is overkill, 
//      and wastes a lot of storage.
//   2. Change `sum` type to `std::uint64_t`, and 
//      use `std::accumulate` to add the numbers.
//   3. Use `std::size_t` for subscripts.
//   4. Delete `using namespace std;`
//   5. Delete variable `k`, which was unused.

#include <cstddef>   // size_t
#include <cstdint>   // uint32_t, uint64_t
#include <iostream>  // cout
#include <iterator>  // cbegin, cend
#include <numeric>   // accumulate

enum : std::uint32_t { x = 2000000u };
enum : std::size_t { array_size = static_cast<std::size_t>(x) + 1u };
std::uint32_t number[array_size];  // `x` is a valid subscript.

std::uint64_t sum()
{
    return std::accumulate(std::cbegin(number), std::cend(number), std::uint64_t{});
}

int main()
{
    number[0u] = 0u;  // Zero-out the first two array elements.
    number[1u] = 0u;
    for (std::size_t i = 2u; i < array_size; i++) //fills in numbers from 2 to 2 million in the array
    {
        number[i] = static_cast<std::uint32_t>(i);
    }
    for (std::size_t j = 2u; j < array_size; j++) //starts eliminating multiples of prime numbers from the grid
    {
        if (number[j] != 0u) //moves through the grid till it finds a number that hasn't been crossed out. ie. isnt zero                            
        {
            for (std::size_t y = j + j; y < array_size; y += j) //when it finds a number, it removes all subsequent multiples of it
            {
                number[y] = 0u;
            }
        }
    }
    std::cout << '\n' << "done. "; //shows that the loop has been completed
    std::cout << "sum = " << sum(); //outputs the sum of the grid
    return 0;
}
// end file: main.cpp

以下部分展示了如何在不使用全局变量的情况下解决此问题。

交错筛法和求和

我最初的方法是直接方法：创建素数向量，然后对其元素求和。函数make_vector_of_primes（未显示）实现埃拉托斯特尼筛算法，来自维基百科。

std::uint64_t calculate_sum_of_primes(std::uint32_t const n)
{
    std::vector<std::uint32_t> const v{ make_vector_of_primes(n) };
    return std::accumulate(v.cbegin(), v.cend(), std::uint64_t{});
}

经过尝试后，我发现您可以交错筛和总和的计算。该代码并不像原始代码那么干净，但程序运行速度快了大约 15% 到 20%。它还使用更少的存储空间，因为素数向量永远不会被计算。

下面的程序包含两个OP中未使用的额外优化。

• 当索引i超过n的平方根时，筛子的外循环停止。
• 筛子的内部循环从索引j开始，设置为i * i，而不是i + i。

main.cpp

// main.cpp
// Requires C++14 or later.
#include <chrono>    // chrono, steady_clock, duration_cast
#include <cmath>     // sqrt
#include <cstddef>   // size_t
#include <cstdint>   // uint32_t, uint64_t
#include <iostream>  // cout
#include <limits>    // numeric_limits
#include <vector>    // vector

namespace
{
    //==================================================================
    // calculate_sum_of_primes
    // Calculate the sum of all prime numbers <= `n`.
    // Preconditions: 
    //   - `n` is at least 2.
    //   - `std::size_t` can hold `n + 1`, without overflowing
    //==================================================================
    std::uint64_t calculate_sum_of_primes(std::uint32_t const n)
    {
        auto const nn{ static_cast<std::size_t>(n) };
        std::vector<bool> is_prime(nn + 1u, true);  // `nn` is a valid subscript
        std::uint64_t sum{};
        is_prime[0u] = false;
        is_prime[1u] = false;
        auto const sqrt_n{ static_cast<std::size_t>(std::sqrt(n)) };
        for (std::size_t i{ 2u }; i <= sqrt_n; ++i) {
            if (is_prime[i]) {
                sum += static_cast<std::uint64_t>(i);
                for (std::size_t j{ i * i }; j <= nn; j += i) {
                    is_prime[j] = false;
                }
            }
        }
        for (std::size_t i{ sqrt_n + 1u }; i <= nn; ++i) {
            if (is_prime[i]) {
                sum += static_cast<std::uint64_t>(i);
            }
        }
        return sum;
    }
    //------------------------------------------------------------------
    void test(std::uint32_t const n)
    {
        using std::chrono::duration_cast;
        using std::chrono::milliseconds;
        auto const start{ std::chrono::steady_clock::now() };
        auto const sum{ calculate_sum_of_primes(n) };
        auto const stop{ std::chrono::steady_clock::now() };
        auto const elapsed_time{ duration_cast<milliseconds>(stop - start) };
        std::cout << 
            "The sum of prime numbers on the interval "
            "[2, " << n << "] is " << sum << ".\n"
            "Elapsed time: " << elapsed_time.count() << "ms\n\n";
    }
    //------------------------------------------------------------------
}
int main()
{
    test(2'000'000u);
    test(std::numeric_limits<std::uint32_t>::max());
    return 0;
}
// end file: main.cpp

输出

第二个示例对可以由 std::uint32_t 类型表示的所有素数求和。其中有超过 2.03 亿个，分散在 32 位可以表示的 40 亿多个数字中。在发布模式下，启用编译器优化后，只需 40 多秒即可找到所有素数并计算它们的总和。

如果搜索空间减少到区区 200 万（如 OP 所示），那么即使是这台笨重的计算机也只需几毫秒即可完成这项工作。

The sum of prime numbers on the interval [2, 2000000] is 142913828922.
Elapsed time: 9ms

The sum of prime numbers on the interval [2, 4294967295] is 425649736193687430.
Elapsed time: 41880ms