-1

我想只使用数组在 C++ 中编写著名的 Eratosthenes 筛，因为它是一个集合，我可以在其中删除一些元素以找出素数。我不想使用 STL（向量，集合）......只是数组！我怎样才能意识到它？

我试图解释为什么我不想使用 STL 集合运算符：我从一开始就在学习 C++，我认为 STL 对程序员当然有用，但建立在标准库上，所以我想使用以前的运算符和命令。我知道使用 STL 一切都会变得更容易。

4

2 回答 2

2

筛选 Eratosthenes效率的关键在于它不会、重复、删除 ⁄ 删除 ⁄ 扔掉 ⁄ 等，因为它列举了复合材料，而只是将它们标记为此类。

保留所有数字保留了我们使用数字的值作为其在此数组中的地址并因此直接寻址它的能力array[n]：当在现代随机存取存储器计算机上实现时（就像整数排序算法一样） ，这就是使筛子的枚举和标记每个素数的倍数有效的原因。

为了使该数组模拟一个集合，我们为每个条目提供两个可能的值，标志：onand off, primeor composite, 1or 0。是的，我们实际上只需要一位而不是字节来表示筛数组中的每个数字，前提是我们在处理它时不删除它们中的任何一个。

顺便说一句，vector<bool>是自动打包的，bool按位表示 s。很方便。

于 2013-08-21T06:28:11.287 回答
1

从算法和数据结构

#include<iostream>
#include<cmath>
#include<cstring>

using namespace std;

void runEratosthenesSieve(int upperBound) {

      int upperBoundSquareRoot = (int)sqrt((double)upperBound);
      bool *isComposite = new bool[upperBound + 1];
      memset(isComposite, 0, sizeof(bool) * (upperBound + 1));

      for (int m = 2; m <= upperBoundSquareRoot; m++) {  
            if (!isComposite[m]) {
                  cout << m << " ";
                  for (int k = m * m; k <= upperBound; k += m)
                        isComposite[k] = true;
            }
      }
      for (int m = upperBoundSquareRoot; m <= upperBound; m++)
            if (!isComposite[m])
                  cout << m << " ";

      delete [] isComposite;
}


int main()
{
 runEratosthenesSieve(1000);
}

您不想使用 STL，但这不是一个好主意

STL 让生活变得更简单。

仍然考虑使用这个实现std::map

int  max = 100;
S sieve;

for(int it=2;it < max;++it)
    sieve.insert(it);

for(S::iterator it = sieve.begin();it != sieve.end();++it)
{
    int  prime   = *it;
    S::iterator x = it;
    ++x;
    while(x != sieve.end())
        if (((*x) % prime) == 0)
            sieve.erase(x++);
        else
            ++x;
}

for(S::iterator it = sieve.begin();it != sieve.end();++it)
 std::cout<<*it<<std::endl;
于 2013-08-18T18:21:21.847 回答