我正在实施Eratosthenes筛。我被困在第一步：决定使用哪种数据结构。简单地说，埃拉托斯梯尼筛从一个连续数字列表开始(例如2,3,4,5，…99100(。然后，某些数字被划掉，再也不考虑了。什么是最好的数据结构？极限(示例中为100(直到运行时才知道，尽管2始终是起始数字。

我看到了一些不同的解决方案。限制n属于mpz_class类型

其中一些信息来自此代码审查问题@Jamal表示"std:：vector确实存在问题"，但没有详细说明。此外，我在某个地方指出，unsigned char的大小保证等于或小于bool，使其成为更好的选择。

tl；dr测量是唯一可以确定的方法，但以下是我对此的想法：

一般情况下

bool primes[n]-一个简单的布尔数组-问题是，它有一个固定的大小，所以如果n在编译时未知，它就不可用。请注意，有些编译器会允许VLA，但这不是标准，应该避免
bool* primes = new bool[n]——也是一个简单的数组，只需要动态分配
CCD_ 18——本质上是CCD_ 19的包装器。可以实现为节省空间的位集
std::bitset<n> primes-节省空间的存储，但遗憾的是，它也具有固定的大小
std::vector<int>或std::vector<usigned char>-与3相同(，只是它没有作为位集进行优化实现

如果要求n在运行时之前是未知的，那么它可以归结为一些std::vector或动态分配的数组。如果n有一个合理的上限，人们仍然可以考虑静态数组。

比特集与数组/矢量

简而言之：位集针对空间进行了优化，基本上每个字节存储8个布尔值，但它们需要逐位操作来提取信息，这需要一些数组/向量中不需要的cpu周期。另请参阅此问题

然而，我不确定比特集的信息密度越高对缓存性能的影响有多大。

如果std::vector<bool>没有被实现为空间有效的比特集，则它可能比std::vector<unsigned char>占用更多的内存，因为sizeof bool可以大于1，从而大于sizeof (unsigned char)。(另请参阅此处(

如果是，则节省空间的实现std::vector<unsigned char>占用更多内存，但可能更快。

sdstd::vector::operator[]不执行绑定检查，因此与bool*相比，不会给阵列访问增加太多性能开销(如果有的话(。此外，一些实现在调试模式下(并且仅在调试模式中(执行边界检查也有好处。CCD_ 33无疑比数组更易于使用。

如果有足够的内存可用，那么CCD_ 34可能是最好的方式。但最终，对不同的n进行基准测试并对进行优化将是唯一可以确定的方法。