#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <ctime>
#include <memory.h>
using namespace std;
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
typedef long long LL;
typedef vector<int> vi;
const int M = 30000;
const int N = M * M;
int Simple()
{
vector<unsigned> a(N / 32 + (N % 32 != 0), 0xFFffFFff);
for (int i = 2; i * i < N; ++i)
if (a[i >> 5] & (1 << (i & 31)))
for (int j = i * i; j < N; j += i)
a[j >> 5] &= ~(1 << (j & 31));
int cnt = 0;
for (int i = 2; i < N; ++i)
if (a[i >> 5] & (1 << (i & 31)))
++cnt;
return cnt;
}
int Another()
{
const int K = 1 << 16;
vector<int> _a(K);
int* a = &_a[0];
FOR(i, K)
a[i] = 1;
vi p;
vi pos;
for (int i = 2; i * i < M; ++i)
if (a[i])
{
for (int j = i * i; j < M; j += i)
a[j] = 0;
}
for (int i = 2; i < M; ++i)
if (a[i])
{
p.push_back(i);
pos.push_back(i * i);
}
int res = 0;
int L = 2;
while (L < N)
{
a = &_a[0] - L;
int R = L;
FOR(i, K)
{
a[R] = 1;
++R;
}
FOR(i, p.size())
{
int x = pos[i];
while (x < R)
{
a[x] = 0;
x += p[i];
}
pos[i] = x;
}
FOR(i, K)
{
if (L < N)
res += a[L];
++L;
}
}
return res;
}
int main()
{
{
time_t tm = clock();
cout << Another() << "\n";
cout << (clock() - tm) / (double)CLOCKS_PER_SEC << "\n";
}
{
time_t tm = clock();
cout << Simple() << "\n";
cout << (clock() - tm) / (double)CLOCKS_PER_SEC << "\n";
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8ZnN0cmVhbT4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxtYXRoLmg+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPG1lbW9yeS5oPgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKI2RlZmluZSBGT1IoaSwgbikgZm9yIChpbnQgaSA9IDA7IGkgPCAoaW50KW47ICsraSkKIAp0eXBlZGVmIGxvbmcgbG9uZyBMTDsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKCmNvbnN0IGludCBNID0gMzAwMDA7CmNvbnN0IGludCBOID0gTSAqIE07CgppbnQgU2ltcGxlKCkKewoJdmVjdG9yPHVuc2lnbmVkPiBhKE4gLyAzMiArIChOICUgMzIgIT0gMCksIDB4RkZmZkZGZmYpOwoJZm9yIChpbnQgaSA9IDI7IGkgKiBpIDwgTjsgKytpKQoJCWlmIChhW2kgPj4gNV0gJiAoMSA8PCAoaSAmIDMxKSkpCgkJCWZvciAoaW50IGogPSBpICogaTsgaiA8IE47IGogKz0gaSkKCQkJCWFbaiA+PiA1XSAmPSB+KDEgPDwgKGogJiAzMSkpOwoJaW50IGNudCA9IDA7Cglmb3IgKGludCBpID0gMjsgaSA8IE47ICsraSkKCQlpZiAoYVtpID4+IDVdICYgKDEgPDwgKGkgJiAzMSkpKQoJCQkrK2NudDsKCXJldHVybiBjbnQ7Cn0KCmludCBBbm90aGVyKCkKewoJY29uc3QgaW50IEsgPSAxIDw8IDE2OwoJdmVjdG9yPGludD4gX2EoSyk7CglpbnQqIGEgPSAmX2FbMF07CgoJRk9SKGksIEspCgkJYVtpXSA9IDE7Cgl2aSBwOwoJdmkgcG9zOwoJZm9yIChpbnQgaSA9IDI7IGkgKiBpIDwgTTsgKytpKQoJCWlmIChhW2ldKQoJCXsKCQkJZm9yIChpbnQgaiA9IGkgKiBpOyBqIDwgTTsgaiArPSBpKQoJCQkJYVtqXSA9IDA7CgkJfQoJZm9yIChpbnQgaSA9IDI7IGkgPCBNOyArK2kpCgkJaWYgKGFbaV0pCgkJewoJCQlwLnB1c2hfYmFjayhpKTsKCQkJcG9zLnB1c2hfYmFjayhpICogaSk7CgkJfQoKCWludCByZXMgPSAwOwoJaW50IEwgPSAyOwoJd2hpbGUgKEwgPCBOKQoJewoJCWEgPSAmX2FbMF0gLSBMOwoKCQlpbnQgUiA9IEw7CgkJRk9SKGksIEspCgkJewoJCQlhW1JdID0gMTsKCQkJKytSOwoJCX0KCQlGT1IoaSwgcC5zaXplKCkpCgkJewoJCQlpbnQgeCA9IHBvc1tpXTsKCQkJd2hpbGUgKHggPCBSKQoJCQl7CgkJCQlhW3hdID0gMDsKCQkJCXggKz0gcFtpXTsKCQkJfQoJCQlwb3NbaV0gPSB4OwoJCX0KCQlGT1IoaSwgSykKCQl7CgkJCWlmIChMIDwgTikKCQkJCXJlcyArPSBhW0xdOwoJCQkrK0w7CgkJfQoJfQoJcmV0dXJuIHJlczsKfQoKaW50IG1haW4oKQp7Cgl7CgkJdGltZV90IHRtID0gY2xvY2soKTsKCQljb3V0IDw8IEFub3RoZXIoKSA8PCAiXG4iOwoJCWNvdXQgPDwgKGNsb2NrKCkgLSB0bSkgLyAoZG91YmxlKUNMT0NLU19QRVJfU0VDIDw8ICJcbiI7Cgl9Cgl7CgkJdGltZV90IHRtID0gY2xvY2soKTsKCQljb3V0IDw8IFNpbXBsZSgpIDw8ICJcbiI7CgkJY291dCA8PCAoY2xvY2soKSAtIHRtKSAvIChkb3VibGUpQ0xPQ0tTX1BFUl9TRUMgPDwgIlxuIjsKCX0KCgoJcmV0dXJuIDA7Cn0=