C++ 优化这个算法

Question

看了一些 Terence Tao 的视频后，我想尝试将算法实现到 c++ 代码中，以找到直到数字 n 的所有素数。在我的第一个版本中，我只是简单地测试了从 2 到 n 的每个整数，看它们是否可以被 2 到 sqrt(n) 的任何整数整除，我让程序在大约 52 秒内找到 1-10,000,000 之间的素数。

尝试优化程序，并实现我现在所知道的埃拉托色尼筛法，我原以为该任务的完成速度会比 51 秒快得多，但遗憾的是，事实并非如此。即使达到 1,000,000 也需要相当长的时间(虽然没有计时)

#include <iostream>
#include <vector>
using namespace std;

void main()
{
    vector<int> tosieve = {};        
    for (int i = 2; i < 1000001; i++) 
    {                                       
        tosieve.push_back(i);               
    }                                       
        for (int j = 0; j < tosieve.size(); j++)
        {
            for (int k = j + 1; k < tosieve.size(); k++)
            {
                if (tosieve[k] % tosieve[j] == 0)
                {
                    tosieve.erase(tosieve.begin() + k);
                }
            }
        }
    //for (int f = 0; f < tosieve.size(); f++)
    //{
    //  cout << (tosieve[f]) << endl;
    //}
    cout << (tosieve.size()) << endl;
    system("pause");
}

是 vector 的重复引用还是什么？为什么这么慢？即使我完全忽略了某些东西(可能是完全初学者:我)我认为用这种可怕的低效方法找到 2 到 1,000,000 之间的素数会比我原来的从 2 到 10,000,000 之间找到它们的方法更快。

希望有人对此有一个明确的答案 - 希望我可以在未来使用大量递归优化程序时使用收集到的任何知识。

Answer 1

问题是“删除”将 vector 中的每个元素都向下移动了一个，这意味着它是一个 O(n) 操作。

共有三种备选方案:

1) 只需将删除的元素标记为“空”(例如，将它们设为 0)。这意味着 future 的通行证必须越过那些空位置，但这并不昂贵。

2) 创建一个新 vector ，并将push_back 新值放入其中。

3) 使用 std::remove_if:这将向下移动元素，但一次完成，因此效率更高。如果您使用 std::remove_if，那么您必须记住它不会调整 vector 本身的大小。