#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;
}
}
}
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;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IE4gPSAxZTg7CmJvb2wgY29tcFtOXTsKdmVjdG9yPGludD5wcmltZXM7CnZvaWQgb2xkc2lldmUoKQp7CiAgICBtZW1zZXQoY29tcCwwLHNpemVvZiBjb21wKTsKICAgIHByaW1lcy5jbGVhcigpOwogICAgCiAgICBib29sIGRvbmUgPSBmYWxzZTsKICAgIGZvcihpbnQgaT0yO2k8TjtpKyspCiAgICAgICAgaWYoIWNvbXBbaV0pCiAgICAgICAgewogICAgICAgICAgICBwcmltZXMucHVzaF9iYWNrKGkpOwogICAgICAgICAgICAKICAgICAgICAgICAgaWYgKGkgKiBpID4gTikgewogICAgICAgICAgICAJZG9uZSA9IHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgCiAgICAgICAgICAgIGlmICghZG9uZSkgZm9yKGludCBqPWkqaTtqPE47ais9aSkKICAgICAgICAgICAgICAgIGNvbXBbal09MTsKICAgICAgICB9Cn0Kdm9pZCBuZXdzaWV2ZSgpCnsKICAgIG1lbXNldChjb21wLDAsc2l6ZW9mIGNvbXApOwogICAgcHJpbWVzLmNsZWFyKCk7CiAgICBmb3IoaW50IGk9MjtpPE47aSsrKQogICAgewogICAgICAgIGlmKCFjb21wW2ldKQogICAgICAgICAgICBwcmltZXMucHVzaF9iYWNrKGkpOwogICAgICAgICAgICBmb3IoaW50IGo9MCxzaT1wcmltZXMuc2l6ZSgpO2o8c2kmJmkqcHJpbWVzW2pdPE47aisrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjb21wW3ByaW1lc1tqXSppXT0xOwogICAgICAgICAgICAgICAgaWYoaSVwcmltZXNbal09PTApYnJlYWs7CiAgICAgICAgICAgIH0KICAgIH0KfQppbnQgbWFpbigpCnsKCWF1dG8gdDAgPSBjbG9jaygpOwogICAgb2xkc2lldmUoKTsKICAgIC8vZm9yKGludCBpPTA7aTwyMDtpKyspY291dDw8cHJpbWVzW2ldPDwnICc7Y291dDw8ZW5kbDsKICAgIGF1dG8gbWlkID0gY2xvY2soKTsKICAgIGNvdXQgPDwgImRpZmYgaXMgIiA8PCAoMS4wICogKG1pZCAtIHQwKSkgLyBDTE9DS1NfUEVSX1NFQyA8PCBlbmRsOwogICAgbmV3c2lldmUoKTsKICAgIC8vZm9yKGludCBpPTA7aTwyMDtpKyspY291dDw8cHJpbWVzW2ldPDwnICc7Y291dDw8ZW5kbDsKICAgIGNvdXQgPDwgImRpZmYgaXMgIiA8PCAoMS4wICogKGNsb2NrKCkgLSBtaWQpKSAvIENMT0NLU19QRVJfU0VDIDw8IGVuZGw7Cn0=