C++ 优化该算法

Question

观看了陶哲轩的一些视频后，我想尝试在 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");
}

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

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

Answer 1

问题是“擦除”会将向量中的每个元素向下移动一位，这意味着它是一个 O(n) 操作。

有以下三种替代选择：

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

2）创建一个新向量，并push_back在其中添加新值。

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