#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();
vector<bool> p(N+1, true);
for(int i=4; i<N; i+=2)
p[i]=false; // erasing the even number
for(int i=3; i*i<N; i+=2) { //computing only odd number
if (p[i]) { //if i is prime then
for(int j=i*i; j<N; j=j+i+i) { // erasing only odd number which is composite
p[j]=false;
}
}
}
// If you erase this you will get even faster
for (int i=2; i < N; ++i)
if (p[i])
primes.push_back(i);
}
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;
}
}
}
int main()
{
auto t0 = clock();
oldsieve();
//for(int i=0;i<20;i++)cout<<primes[i]<<' ';cout<<endl;
auto mid = clock();
cout << "diff is " << (1.0 * (mid - t0)) / CLOCKS_PER_SEC << endl;
newsieve();
//for(int i=0;i<20;i++)cout<<primes[i]<<' ';cout<<endl;
cout << "diff is " << (1.0 * (clock() - mid)) / CLOCKS_PER_SEC << endl;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IE4gPSAxZTg7CmJvb2wgY29tcFtOXTsKdmVjdG9yPGludD5wcmltZXM7CnZvaWQgb2xkc2lldmUoKQp7CiAgICBtZW1zZXQoY29tcCwwLHNpemVvZiBjb21wKTsKICAgIHByaW1lcy5jbGVhcigpOwogICAgCiAgICB2ZWN0b3I8Ym9vbD4gcChOKzEsIHRydWUpOwogICAgCiAgICBmb3IoaW50IGk9NDsgaTxOOyBpKz0yKQoJCXBbaV09ZmFsc2U7IC8vIGVyYXNpbmcgdGhlIGV2ZW4gbnVtYmVyCglmb3IoaW50IGk9MzsgaSppPE47IGkrPTIpIHsgLy9jb21wdXRpbmcgb25seSBvZGQgbnVtYmVyCgkJaWYgKHBbaV0pIHsgLy9pZiBpIGlzIHByaW1lIHRoZW4KCQkJZm9yKGludCBqPWkqaTsgajxOOyBqPWoraStpKSB7IC8vIGVyYXNpbmcgb25seSBvZGQgbnVtYmVyIHdoaWNoIGlzIGNvbXBvc2l0ZQoJCQkJcFtqXT1mYWxzZTsKCQkJfQoJCX0KCX0KCQoJLy8gSWYgeW91IGVyYXNlIHRoaXMgeW91IHdpbGwgZ2V0IGV2ZW4gZmFzdGVyCglmb3IgKGludCBpPTI7IGkgPCBOOyArK2kpCgkJaWYgKHBbaV0pCgkJCXByaW1lcy5wdXNoX2JhY2soaSk7Cn0Kdm9pZCBuZXdzaWV2ZSgpCnsKICAgIG1lbXNldChjb21wLDAsc2l6ZW9mIGNvbXApOwogICAgcHJpbWVzLmNsZWFyKCk7CiAgICBmb3IoaW50IGk9MjtpPE47aSsrKQogICAgewogICAgICAgIGlmKCFjb21wW2ldKQogICAgICAgICAgICBwcmltZXMucHVzaF9iYWNrKGkpOwogICAgICAgICAgICBmb3IoaW50IGo9MCxzaT1wcmltZXMuc2l6ZSgpO2o8c2kmJmkqcHJpbWVzW2pdPE47aisrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjb21wW3ByaW1lc1tqXSppXT0xOwogICAgICAgICAgICAgICAgaWYoaSVwcmltZXNbal09PTApYnJlYWs7CiAgICAgICAgICAgIH0KICAgIH0KfQppbnQgbWFpbigpCnsKCWF1dG8gdDAgPSBjbG9jaygpOwogICAgb2xkc2lldmUoKTsKICAgIC8vZm9yKGludCBpPTA7aTwyMDtpKyspY291dDw8cHJpbWVzW2ldPDwnICc7Y291dDw8ZW5kbDsKICAgIGF1dG8gbWlkID0gY2xvY2soKTsKICAgIGNvdXQgPDwgImRpZmYgaXMgIiA8PCAoMS4wICogKG1pZCAtIHQwKSkgLyBDTE9DS1NfUEVSX1NFQyA8PCBlbmRsOwogICAgbmV3c2lldmUoKTsKICAgIC8vZm9yKGludCBpPTA7aTwyMDtpKyspY291dDw8cHJpbWVzW2ldPDwnICc7Y291dDw8ZW5kbDsKICAgIGNvdXQgPDwgImRpZmYgaXMgIiA8PCAoMS4wICogKGNsb2NrKCkgLSBtaWQpKSAvIENMT0NLU19QRVJfU0VDIDw8IGVuZGw7Cn0=