#include<bits/stdc++.h>
using namespace std;
const int N = 1e8;
bool comp[N];
vector<int>primes;
void oldsieve()
{
memset(comp,0,sizeof comp);
primes.clear();
bool done = false;
for(int i=2;i<N;i++)
if(!comp[i])
{
primes.push_back(i);
if (i * i > N) {
done = true;
}
if (!done) for(int j=i*i;j<N;j+=i)
comp[j]=1;
}
}
void newsieve()
{
memset(comp,0,sizeof comp);
primes.clear();
for(int i=2;i<N;i++)
{
if(!comp[i])
primes.push_back(i);
for(int j=0,si=primes.size();j<si&&i*primes[j]<N;j++)
{
comp[primes[j]*i]=1;
if(i%primes[j]==0)break;
}
}
}
void segmented_sieve() {
int n = N;
const int S = 10000;
primes.clear();
vector<int> Ps;
int nsqrt = sqrt(n);
vector<char> is_prime(nsqrt + 1, true);
for (int i = 2; i <= nsqrt; i++) {
if (is_prime[i]) {
Ps.push_back(i);
for (int j = i * i; j <= nsqrt; j += i)
is_prime[j] = false;
}
}
int result = 0;
vector<char> block(S);
for (int k = 0; k * S <= n; k++) {
fill(block.begin(), block.end(), true);
int start = k * S;
for (int p : Ps) {
int start_idx = (start + p - 1) / p;
int j = max(start_idx, p) * p - start;
for (; j < S; j += p)
block[j] = false;
}
if (k == 0)
block[0] = block[1] = false;
for (int i = 0; i < S && start + i <= n; i++) {
if (block[i])
primes.push_back(start+i);
}
};
}
int main()
{
auto t0 = clock();
oldsieve();
auto t1 = clock();
auto primes_old = primes;
primes.clear();
cout << "old: " << (1.0 * (t1 - t0)) / CLOCKS_PER_SEC << endl;
t0 = clock();
newsieve();
t1 = clock();
auto primes_new = primes;
primes.clear();
cout << "new: " << (1.0 * (t1 - t0)) / CLOCKS_PER_SEC << endl;
assert(primes_new == primes_old);
t0 = clock();
segmented_sieve();
t1 = clock();
auto primes_seg = primes;
primes.clear();
cout << "segmented_sieve: " << (1.0 * (t1 - t0)) / CLOCKS_PER_SEC << endl;
assert(primes_seg == primes_old);
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IE4gPSAxZTg7CmJvb2wgY29tcFtOXTsKdmVjdG9yPGludD5wcmltZXM7CnZvaWQgb2xkc2lldmUoKQp7CiAgICBtZW1zZXQoY29tcCwwLHNpemVvZiBjb21wKTsKICAgIHByaW1lcy5jbGVhcigpOwogICAgCiAgICBib29sIGRvbmUgPSBmYWxzZTsKICAgIGZvcihpbnQgaT0yO2k8TjtpKyspCiAgICAgICAgaWYoIWNvbXBbaV0pCiAgICAgICAgewogICAgICAgICAgICBwcmltZXMucHVzaF9iYWNrKGkpOwogICAgICAgICAgICAKICAgICAgICAgICAgaWYgKGkgKiBpID4gTikgewogICAgICAgICAgICAJZG9uZSA9IHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgCiAgICAgICAgICAgIGlmICghZG9uZSkgZm9yKGludCBqPWkqaTtqPE47ais9aSkKICAgICAgICAgICAgICAgIGNvbXBbal09MTsKICAgICAgICB9Cn0Kdm9pZCBuZXdzaWV2ZSgpCnsKICAgIG1lbXNldChjb21wLDAsc2l6ZW9mIGNvbXApOwogICAgcHJpbWVzLmNsZWFyKCk7CiAgICBmb3IoaW50IGk9MjtpPE47aSsrKQogICAgewogICAgICAgIGlmKCFjb21wW2ldKQogICAgICAgICAgICBwcmltZXMucHVzaF9iYWNrKGkpOwogICAgICAgICAgICBmb3IoaW50IGo9MCxzaT1wcmltZXMuc2l6ZSgpO2o8c2kmJmkqcHJpbWVzW2pdPE47aisrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjb21wW3ByaW1lc1tqXSppXT0xOwogICAgICAgICAgICAgICAgaWYoaSVwcmltZXNbal09PTApYnJlYWs7CiAgICAgICAgICAgIH0KICAgIH0KfQp2b2lkIHNlZ21lbnRlZF9zaWV2ZSgpIHsKCWludCBuID0gTjsKICAgIGNvbnN0IGludCBTID0gMTAwMDA7CgoJcHJpbWVzLmNsZWFyKCk7CiAgICB2ZWN0b3I8aW50PiBQczsKICAgIGludCBuc3FydCA9IHNxcnQobik7CiAgICB2ZWN0b3I8Y2hhcj4gaXNfcHJpbWUobnNxcnQgKyAxLCB0cnVlKTsKICAgIGZvciAoaW50IGkgPSAyOyBpIDw9IG5zcXJ0OyBpKyspIHsKICAgICAgICBpZiAoaXNfcHJpbWVbaV0pIHsKICAgICAgICAgICAgUHMucHVzaF9iYWNrKGkpOwogICAgICAgICAgICBmb3IgKGludCBqID0gaSAqIGk7IGogPD0gbnNxcnQ7IGogKz0gaSkKICAgICAgICAgICAgICAgIGlzX3ByaW1lW2pdID0gZmFsc2U7CiAgICAgICAgfQogICAgfQoKICAgIGludCByZXN1bHQgPSAwOwogICAgdmVjdG9yPGNoYXI+IGJsb2NrKFMpOwogICAgZm9yIChpbnQgayA9IDA7IGsgKiBTIDw9IG47IGsrKykgewogICAgICAgIGZpbGwoYmxvY2suYmVnaW4oKSwgYmxvY2suZW5kKCksIHRydWUpOwogICAgICAgIGludCBzdGFydCA9IGsgKiBTOwogICAgICAgIGZvciAoaW50IHAgOiBQcykgewogICAgICAgICAgICBpbnQgc3RhcnRfaWR4ID0gKHN0YXJ0ICsgcCAtIDEpIC8gcDsKICAgICAgICAgICAgaW50IGogPSBtYXgoc3RhcnRfaWR4LCBwKSAqIHAgLSBzdGFydDsKICAgICAgICAgICAgZm9yICg7IGogPCBTOyBqICs9IHApCiAgICAgICAgICAgICAgICBibG9ja1tqXSA9IGZhbHNlOwogICAgICAgIH0KICAgICAgICBpZiAoayA9PSAwKQogICAgICAgICAgICBibG9ja1swXSA9IGJsb2NrWzFdID0gZmFsc2U7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBTICYmIHN0YXJ0ICsgaSA8PSBuOyBpKyspIHsKICAgICAgICAgICAgaWYgKGJsb2NrW2ldKQogICAgICAgICAgICAgICAgcHJpbWVzLnB1c2hfYmFjayhzdGFydCtpKTsKICAgICAgICB9CiAgICB9Owp9CgppbnQgbWFpbigpCnsKCWF1dG8gdDAgPSBjbG9jaygpOwogICAgb2xkc2lldmUoKTsKICAgIGF1dG8gdDEgPSBjbG9jaygpOwogICAgYXV0byBwcmltZXNfb2xkID0gcHJpbWVzOwogICAgcHJpbWVzLmNsZWFyKCk7CiAgICBjb3V0IDw8ICJvbGQ6ICIgPDwgKDEuMCAqICh0MSAtIHQwKSkgLyBDTE9DS1NfUEVSX1NFQyA8PCBlbmRsOwogICAgCiAgICB0MCA9IGNsb2NrKCk7CiAgICBuZXdzaWV2ZSgpOwogICAgdDEgPSBjbG9jaygpOwogICAgYXV0byBwcmltZXNfbmV3ID0gcHJpbWVzOwogICAgcHJpbWVzLmNsZWFyKCk7CiAgICBjb3V0IDw8ICJuZXc6ICIgPDwgKDEuMCAqICh0MSAtIHQwKSkgLyBDTE9DS1NfUEVSX1NFQyA8PCBlbmRsOwogICAgYXNzZXJ0KHByaW1lc19uZXcgPT0gcHJpbWVzX29sZCk7CiAgICAgICAgCiAgICB0MCA9IGNsb2NrKCk7CiAgICBzZWdtZW50ZWRfc2lldmUoKTsKICAgIHQxID0gY2xvY2soKTsKICAgIGF1dG8gcHJpbWVzX3NlZyA9IHByaW1lczsKICAgIHByaW1lcy5jbGVhcigpOwogICAgY291dCA8PCAic2VnbWVudGVkX3NpZXZlOiAiIDw8ICgxLjAgKiAodDEgLSB0MCkpIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgZW5kbDsKICAgIGFzc2VydChwcmltZXNfc2VnID09IHByaW1lc19vbGQpOwp9