c++ 埃拉托色尼筛法我的代码很慢

Question

我试图找到 4 亿以下的素数，但即使只有 4000 万，我的代码也需要 8 秒才能运行。我做错了什么？

我该怎么做才能让它更快？

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int main()
{
    vector<bool> k;                         
    vector<long long int> c;                
    for (int i=2;i<40000000;i++)
    {
        k.push_back(true);                  
        c.push_back(i);
    }

    for ( int i=0;i<sqrt(40000000)+1;i++)                            
    {                                                               
        if (k[i]==true)                                              
       {                                                            
           for (int j=i+c[i];j<40000000;j=j+c[i])                  
           {                                                       
               k[j]=false; 
           }
       }
    }
    vector <long long int> arr;
    for ( int i=0;i<40000000-2;i++)
    {
        if (k[i]==true)
        {
            arr.push_back(c[i]);
        }
    }
    cout << arr.size() << endl ;
    return 0;
}

Answer 1

我通过改变两件事在我的电脑上从 10 秒减少到运行半秒。首先，我猜你没有在启用优化的情况下编译它。这对我来说从 10 秒减少到 1 秒。其次，矢量 c 是不必要的。代码中任何有 c[i] 的地方都可以用 i+2 替换它。这将使它运行快两倍。

Answer 2

删除向量 c，你不需要它。
在开始时创建已知大小的向量 k。从性能的角度来看，通过调用 push_back() 将元素重复添加到向量中是一个非常糟糕的主意，因为它会导致重复的内存重新分配和复制。
http://primesieve.org/segmented_sieve.html - 用于灵感的分段版本。
您可以跳过处理 2 和 3 的倍数。link from code review
您似乎在编译器优化标志设置方面遇到了一些问题。也许您没有将配置从调试更改为发布。您的发布加速与调试相比是多少？

Answer 3

我在下面分析了您的代码以及一个简单的调整。调整速度是原来的两倍多：

    auto start = std::chrono::high_resolution_clock::now();

    //original version
    vector<bool> k;                         
    vector<long long int> c;                
    for (int i=2;i<40000000;i++)
      {
        k.push_back(true);                  
        c.push_back(i);
      }

    for ( int i=0;i<sqrt(40000000)+1;i++)                            
      {                                                               
        if (k[i]==true)                                              
          {                                                            
            for (int j=i+c[i];j<40000000;j=j+c[i])                  
              {                                                       
                k[j]=false; 
              }
          }
      }
    vector <long long int> arr;
    for ( int i=0;i<40000000-2;i++)
      {
        if (k[i]==true)
          {
            arr.push_back(c[i]);
          }
      }
    cout << arr.size() << endl ;


    auto end1 = std::chrono::high_resolution_clock::now();
    std::cout << "Elapsed = " << 
      std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start).count() <<
      std::endl;

  }

  {

    auto begin = std::chrono::high_resolution_clock::now();

    //new version

    const long limit{40000000};
    vector<bool> k(limit-1,true);  

    //k[0] is the number 0
    k[0]=false; k[1]=false;

    auto sq = sqrt(limit) + 1;

    //start at the number 2
    for ( int i=2;i<sq;i++)                            
      {                                                               
        if (k[i]==true)                                              
          {                                                            
            for (int j=i+i;j<limit;j+=i)                  
              {                                                       
                k[j]=false; 
              }
          }
      }


    vector <long long int> arr;
    for ( int i=0;i<limit-2;i++)
      {
        if (k[i]==true)
          {
            arr.push_back(i);
          }
      }
    cout << arr.size() << endl ;



    auto stop = std::chrono::high_resolution_clock::now();
    std::cout << "Elapsed = " << 
      std::chrono::duration_cast<std::chrono::milliseconds>(stop - begin).count() <<
      std::endl;

  }

这是调试模式下的输出（以毫秒为单位）：

2433654
Elapsed = 5787
2433654
Elapsed = 2432

两者的结果相同，第二个快得多。

这是另一个使用一些不错的 C++ 功能的版本（需要更少的代码），它比上面的第二个版本快大约 11%：

    auto begin = std::chrono::high_resolution_clock::now();

    const long limit{40000000};
    vector<int> k(limit-1,0);

    //fill with sequence of integers
    std::iota(k.begin(),k.end(),0);

    //k[0] is the number 0
    //integers reset to 0 are not prime
    k[0]=0; k[1]=0;

    auto sq = sqrt(limit) + 1;

    //start at the number 2
    for (int i=2;i<sq;i++)                            
      {                                                               
        if (k[i])
          {                                                            
            for (int j=i+i;j<limit;j+=i)                  
              {                                                       
                k[j]=0; 
              }
          }
      }

    auto results = std::remove(k.begin(),k.end(),0);

    cout << results - k.begin() << endl ;


    auto stop = std::chrono::high_resolution_clock::now();
    std::cout << "Elapsed = " << 
      std::chrono::duration_cast<std::chrono::milliseconds>(stop - begin).count() <<
      std::endl;

  }

请注意，在您的原始版本中，您在三个不同的地方 push_back，而这种现代习语的使用在对 vector 进行操作时根本不会使用 push_back。

在本例中，vector 属于 int，因此您在完成后可以获得实际的素数列表。

输出：

2433654
Elapsed = 2160

以上均为Debug模式编号

在Release模式下，最好结合上面的第二和第三种技术，使用带有布尔向量的数字，如果你不关心最后实际的素数是什么：

2433654
Elapsed = 1098
2433654
Elapsed bool remove= 410
2433654
Elapsed = 779

请注意，在我使用了 5 年的笔记本电脑上，您的原始代码在发布模式下只需要大约 1 秒，因此您可能运行处于调试模式。

c++ 埃拉托色尼筛法我的代码很慢

c++ sieve of Eratosthenes my code is slow

c++

time-complexity

sieve-of-eratosthenes