Eratosthenes Sieve is cool, but deprecated ? Why not use my Prime class ? it has an incrementation method, does not not use division.
Prime class describes a number through its congruences to lower primes. Incrementing a prime is to increase all congruences, a new congruence is created if the integer is prime (all congruences -modulos_- differ from 0).
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
class Prime {
public :
Prime () : n_ (2), modulos_ (std::vector<std::pair<int, int> > ())
{
if (!modulos_.capacity ()) modulos_.reserve (100000000);
std::pair<int, int> p (2, 0);
modulos_.push_back (p);
}
~Prime () {}
Prime (const Prime& i) : n_ (i.n_), modulos_ (i.modulos_)
{}
bool operator == (const Prime& n) const {
return (n_ == n.n_);
}
bool operator != (const Prime& n) const {
return !operator == (n);
}
Prime& operator = (const Prime& i) {
n_ = i.n_,
modulos_ = i.modulos_;
return *this;
}
void write (std::ostream& os) const {
os << n_;
}
void operator ++ () {
int prime (1);
do {
++n_;
prime = 1;
std::for_each (modulos_.begin (), modulos_.end (), [&prime] (std::pair<int, int>& p) {
++p.second;
if (p.first == p.second) {
p.second = 0;
prime = 0;
}
});
}
while (!prime);
std::pair<int, int> p (n_, 0);
modulos_.push_back (p);
}
bool operator < (const int& s) const {
return n_ < s;
}
private :
int n_;
std::vector<std::pair<int, int> > modulos_;
};
Usage :
int main (int, char**) {
Prime p;
do {
p.write (std::cout);
std::cout << std::endl;
++p;
}
while (p < 20);
}
Results :
2
3
5
7
11
13
17
19
