筛链生成素数C++

Question

我正在尝试将找到的每个素数输入到 "sieve" 对象链中。下面的代码实现了我最终想要做的，但是每个筛子（质数）class 是手动实现的（检查后续数字是否可以被存储的质数整除然后它们应该被丢弃，否则它们应该被转发到链中的下一个筛子），有没有一种方法可以动态地执行此操作，即每次找到新的素数时，我都必须创建一个筛子对象。非常感谢任何帮助。

#include <iostream>
#include <stdio.h>

using namespace std;

class Sieve
{
public:
    virtual int NextNumber () = 0;
};

class SourceSieve: public Sieve
{
public:
    SourceSieve () : _i (2) {}
    int NextNumber ();
private:
    int _i;
};

class Sieve2: public Sieve
{
public:
    Sieve2 (Sieve & src) : _src (src) { }
    int NextNumber ();
private:
    Sieve & _src;
};

class Sieve3: public Sieve
{
public:
    Sieve3 (Sieve & src) : _src (src) {}
    int NextNumber ();
private:
    Sieve & _src;
};

class Sieve5: public Sieve
{
public:
    Sieve5 (Sieve & src) : _src (src) {}
    int NextNumber ();
private:
    Sieve & _src;
};

class Sieve7: public Sieve
{
public:
    Sieve7 (Sieve & src) : _src (src) {}
    int NextNumber ();
private:
    Sieve & _src;
};
//Here's the implementation of NextNumber for SourceSieve and Sieve2:
int SourceSieve::NextNumber ()
{
    if (_i > 100)
        return -1; // end
    return _i++;
}

int Sieve2::NextNumber ()
{
    int i;
    do
    {
        i = _src.NextNumber ();
    } while (i % 2 == 0 && i != 2 && i != -1);
    return i;
}

int Sieve3::NextNumber ()
{
    int i;
    do
    {
        i = _src.NextNumber ();
    } while (i % 3 == 0 && i != 3 && i != -1);
    return i;
}

int Sieve5::NextNumber ()
{
    int i;
    do
    {
        i = _src.NextNumber ();
    } while (i % 5 == 0 && i != 5 && i != -1);
    return i;
}
int Sieve7::NextNumber ()
{
    int i;
    do
    {
        i = _src.NextNumber ();
    } while (i % 7 == 0 && i != 7 && i != -1);
    return i;
}


int main ()
{
    SourceSieve src;
    Sieve2 s2(src);
    Sieve3 s3 (s2);
    Sieve5 s5 (s3);
    Sieve7 s7 (s5);

    int i = 1;
    for (;;)
    {

        i = s7.NextNumber();
        if (i == -1)
            break;
        std::cout << i <<" ";


    }
}

Answer 1

如果我没看错你的问题，你可以将所有 Sieve2、Sieve3、... 类替换为：

class PrimeSieve : public Sieve
{
public:
  PrimeSieve(Sieve& src, int prime)
  : Sieve()
  , src_(src)
  , prime_(prime) {
  }

  override int NextNumber () {
    int i;
    do
    {
      i = _src.NextNumber ();
    } while (i % 2 == 0 && i != 2 && i != -1);
    return i;
  }

private:
  Sieve & src_;
  int prime_;
};

那么，您的调用代码将是：

int main ()
{
  SourceSieve src;
  vector<PrimeSieve> sieves;
  sieves.emplace_back(src, 2);

  int i = 1;
  for (;;)
  {
    auto& currentLastSieve = sieves.back();
    i = currentLastSieve.NextNumber();
    if (i == -1)
      break;
    sieves.emplace_back(currentLastSieve. i);
    std::cout << i <<" ";
  }
}

但是，我宁愿将排序逻辑放在您的 Sieve 类之外，放入更容易推理的东西中，例如外部容器。

筛链生成素数C++

Chain of Sieves to generate prime numbers C++

c++

primes

sieve