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

问题描述 投票：0回答：3

解决问题时遇到一点困难：“计算两百万以下的素数之和”。我正在使用“埃拉托斯特尼筛法”。我的方法可以很好地查找 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;
}
c++ sieve-of-eratosthenes
3个回答
3
投票

我不确定 int 是否足以保存答案...它可能大于 32 位值。 尝试始终使用 

long long
。

1
投票

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

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

如有疑问，请告诉

0
投票

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

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

尝试在全文中使用 long long。

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

std::uint32_t

 可以节省大量存储空间。

我的偏好是使用标头

<cstdint>

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

如果您继续使用OP使用的“全局”变量，则会给出以下声明。

enum

 用于创建编译时常量：

enum : std::uint32_t { x = 2'000'000u }; enum : std::size_t { array_size = x + 1u }; std::uint32_t number[array_size]; // `x` is a valid subscript. 
请参阅下文，了解消除全局变量的方法。


使用 
std::accumulate
 添加数字


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




  • 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 = 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
（未显示）实现了 
Sieve of Eratosthenes 算法，来自维基百科。

enum : std::uint32_t { n = 2'000'000u };
std::vector<std::uint32_t> const v{ make_vector_of_primes(n) };
std::uint64_t const sum{ std::accumulate(v.cbegin(), v.cend(), std::uint64_t{}) };

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


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




    当索引
  • i
    超过
    n
    的平方根时，筛子外循环停止。
    

    • 筛子的内循环从索引
  • j
    开始，设置为
    i * i
    ，而不是
    i + i
    。
    

    • 

主.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 <string>    // to_string
#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) };
        auto const elapsed{ std::to_string(elapsed_time.count()) + "ms" };
        std::cout << 
            "The sum of prime numbers on the interval "
            "[2, " << std::to_string(n) << "] "
            "is " << std::to_string(sum) << ".\n"
            "Elapsed time: " << elapsed << "\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

    

	

    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.