#include <algorithm>
#include <assert.h>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <vector>
 
class prime_iterator
{
public:
    prime_iterator() : m_next(2), m_max(INT_MAX)
    {
    }
    prime_iterator(int n) : m_next(INT_MAX), m_max(n)
    {
        if ((size_t)n/2 >= m_sieve.size())
        {
            int base = (int) sqrt((double)n);
            prime_iterator end(base);
            m_sieve.resize(n/2 + 1, true);
            prime_iterator p;
            for (++p;  p != end;  ++p)
            {
                int first = std::max(*p, (base + *p - 1) / *p);
                first = (first & ~1) + 1;
                for (int i = first * *p;  i <= n;  i += 2 * *p)
                {
                    m_sieve[i/2] = false;
                }
            }
        }
    }
    int operator*() const
    {
        assert((size_t)m_next/2 < m_sieve.size() && m_sieve[m_next/2]);
        return m_next;
    }
    prime_iterator & operator++()
    {
        size_t i, end = m_sieve.size();
        for (i = (m_next - 1)/2 + 1;  i < end && !m_sieve[i];  ++i)
            ;
        m_next = i*2 + 1;
        return *this;
    }
    bool operator==(const prime_iterator & pi) const
    {
        return m_next == pi.m_next || m_next > pi.m_max || pi.m_next > m_max;
    }
    bool operator!=(const prime_iterator & pi) const
    {
        return !operator==(pi);
    }
private:
    int m_next;
    int m_max;
 
    static std::vector<bool> m_sieve;
};
 
//                          0/1    2/3   5     7     9
static bool sieve_init[] = {false, true, true, true, false};
std::vector<bool> prime_iterator::m_sieve = std::vector<bool>(sieve_init, sieve_init + sizeof(sieve_init) / sizeof(sieve_init[0]));
 
 
int main(int argc, char* argv[])
{
    for (prime_iterator p, end = prime_iterator(1000);  p != end;  ++p)
        std::cout << *p << std::endl;
	return 0;
}
 

I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGFzc2VydC5oPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxsaW1pdHMuaD4KI2luY2x1ZGUgPG1hdGguaD4KI2luY2x1ZGUgPHZlY3Rvcj4KCmNsYXNzIHByaW1lX2l0ZXJhdG9yCnsKcHVibGljOgogICAgcHJpbWVfaXRlcmF0b3IoKSA6IG1fbmV4dCgyKSwgbV9tYXgoSU5UX01BWCkKICAgIHsKICAgIH0KICAgIHByaW1lX2l0ZXJhdG9yKGludCBuKSA6IG1fbmV4dChJTlRfTUFYKSwgbV9tYXgobikKICAgIHsKICAgICAgICBpZiAoKHNpemVfdCluLzIgPj0gbV9zaWV2ZS5zaXplKCkpCiAgICAgICAgewogICAgICAgICAgICBpbnQgYmFzZSA9IChpbnQpIHNxcnQoKGRvdWJsZSluKTsKICAgICAgICAgICAgcHJpbWVfaXRlcmF0b3IgZW5kKGJhc2UpOwogICAgICAgICAgICBtX3NpZXZlLnJlc2l6ZShuLzIgKyAxLCB0cnVlKTsKICAgICAgICAgICAgcHJpbWVfaXRlcmF0b3IgcDsKICAgICAgICAgICAgZm9yICgrK3A7ICBwICE9IGVuZDsgICsrcCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IGZpcnN0ID0gc3RkOjptYXgoKnAsIChiYXNlICsgKnAgLSAxKSAvICpwKTsKICAgICAgICAgICAgICAgIGZpcnN0ID0gKGZpcnN0ICYgfjEpICsgMTsKICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSBmaXJzdCAqICpwOyAgaSA8PSBuOyAgaSArPSAyICogKnApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgbV9zaWV2ZVtpLzJdID0gZmFsc2U7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBpbnQgb3BlcmF0b3IqKCkgY29uc3QKICAgIHsKICAgICAgICBhc3NlcnQoKHNpemVfdCltX25leHQvMiA8IG1fc2lldmUuc2l6ZSgpICYmIG1fc2lldmVbbV9uZXh0LzJdKTsKICAgICAgICByZXR1cm4gbV9uZXh0OwogICAgfQogICAgcHJpbWVfaXRlcmF0b3IgJiBvcGVyYXRvcisrKCkKICAgIHsKICAgICAgICBzaXplX3QgaSwgZW5kID0gbV9zaWV2ZS5zaXplKCk7CiAgICAgICAgZm9yIChpID0gKG1fbmV4dCAtIDEpLzIgKyAxOyAgaSA8IGVuZCAmJiAhbV9zaWV2ZVtpXTsgICsraSkKICAgICAgICAgICAgOwogICAgICAgIG1fbmV4dCA9IGkqMiArIDE7CiAgICAgICAgcmV0dXJuICp0aGlzOwogICAgfQogICAgYm9vbCBvcGVyYXRvcj09KGNvbnN0IHByaW1lX2l0ZXJhdG9yICYgcGkpIGNvbnN0CiAgICB7CiAgICAgICAgcmV0dXJuIG1fbmV4dCA9PSBwaS5tX25leHQgfHwgbV9uZXh0ID4gcGkubV9tYXggfHwgcGkubV9uZXh0ID4gbV9tYXg7CiAgICB9CiAgICBib29sIG9wZXJhdG9yIT0oY29uc3QgcHJpbWVfaXRlcmF0b3IgJiBwaSkgY29uc3QKICAgIHsKICAgICAgICByZXR1cm4gIW9wZXJhdG9yPT0ocGkpOwogICAgfQpwcml2YXRlOgogICAgaW50IG1fbmV4dDsKICAgIGludCBtX21heDsKCiAgICBzdGF0aWMgc3RkOjp2ZWN0b3I8Ym9vbD4gbV9zaWV2ZTsKfTsKCi8vICAgICAgICAgICAgICAgICAgICAgICAgICAwLzEgICAgMi8zICAgNSAgICAgNyAgICAgOQpzdGF0aWMgYm9vbCBzaWV2ZV9pbml0W10gPSB7ZmFsc2UsIHRydWUsIHRydWUsIHRydWUsIGZhbHNlfTsKc3RkOjp2ZWN0b3I8Ym9vbD4gcHJpbWVfaXRlcmF0b3I6Om1fc2lldmUgPSBzdGQ6OnZlY3Rvcjxib29sPihzaWV2ZV9pbml0LCBzaWV2ZV9pbml0ICsgc2l6ZW9mKHNpZXZlX2luaXQpIC8gc2l6ZW9mKHNpZXZlX2luaXRbMF0pKTsKCgppbnQgbWFpbihpbnQgYXJnYywgY2hhciogYXJndltdKQp7CiAgICBmb3IgKHByaW1lX2l0ZXJhdG9yIHAsIGVuZCA9IHByaW1lX2l0ZXJhdG9yKDEwMDApOyAgcCAhPSBlbmQ7ICArK3ApCiAgICAgICAgc3RkOjpjb3V0IDw8ICpwIDw8IHN0ZDo6ZW5kbDsKCXJldHVybiAwOwp9Cg==