#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define trav(i, a) for(auto& i: a)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define si(a) ((int)(a).size())
#define ins insert
#define pb push_back
#define mp make_pair
#define f first
#define s second
const int MOD = 1e9 + 7;
const int INF = 1e18;
const string nl = "\n";
const int N = 1e7;
void oldsieve() {
vector<bool> prime(N + 1, 1);
vector<int> primes;
prime[0] = prime[1] = 0;
for(int i = 2; i * i <= N; ++i) {
if(prime[i]) {
primes.pb(i);
for(int j = i * i; j <= N; j += i) {
prime[j] = 0;
}
}
}
}
void newsieve(int n = N) {
std::vector <int> prime;
bool is_composite[n + 1];
std::fill (is_composite, is_composite + n, false);
for (int i = 2; i < n; ++i) {
if (!is_composite[i]) prime.push_back (i);
for (int j = 0; j < prime.size () && i * prime[j] < n; ++j) {
is_composite[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
auto t = clock();
oldsieve();
auto t1 = clock();
cout << "oldsieve: " << (1.0 * (t1 - t)) / CLOCKS_PER_SEC << nl;
t = clock();
newsieve();
t1 = clock();
cout << "newsieve: " << (1.0 * (t1 - t)) / CLOCKS_PER_SEC << nl;
}
I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKI2RlZmluZSBpbnQgaW50NjRfdAojZGVmaW5lIHRyYXYoaSwgYSkgZm9yKGF1dG8mIGk6IGEpCiNkZWZpbmUgYWxsKGEpIGEuYmVnaW4oKSwgYS5lbmQoKQojZGVmaW5lIHJhbGwoYSkgYS5yYmVnaW4oKSwgYS5yZW5kKCkKI2RlZmluZSBzaShhKSAoKGludCkoYSkuc2l6ZSgpKQojZGVmaW5lIGlucyBpbnNlcnQKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBmIGZpcnN0CiNkZWZpbmUgcyBzZWNvbmQKIApjb25zdCBpbnQgTU9EID0gMWU5ICsgNzsKY29uc3QgaW50IElORiA9IDFlMTg7CmNvbnN0IHN0cmluZyBubCA9ICJcbiI7CmNvbnN0IGludCBOID0gMWU3OwogCnZvaWQgb2xkc2lldmUoKSB7Cgl2ZWN0b3I8Ym9vbD4gcHJpbWUoTiArIDEsIDEpOwoJdmVjdG9yPGludD4gcHJpbWVzOwoJcHJpbWVbMF0gPSBwcmltZVsxXSA9IDA7Cglmb3IoaW50IGkgPSAyOyBpICogaSA8PSBOOyArK2kpIHsKCQlpZihwcmltZVtpXSkgewoJCQlwcmltZXMucGIoaSk7CgkJCWZvcihpbnQgaiA9IGkgKiBpOyBqIDw9IE47IGogKz0gaSkgewoJCQkJcHJpbWVbal0gPSAwOwoJCQl9CgkJfQoJfQp9CiAKdm9pZCBuZXdzaWV2ZShpbnQgbiA9IE4pIHsKCXN0ZDo6dmVjdG9yIDxpbnQ+IHByaW1lOwoJYm9vbCBpc19jb21wb3NpdGVbbiArIDFdOwoJc3RkOjpmaWxsIChpc19jb21wb3NpdGUsIGlzX2NvbXBvc2l0ZSArIG4sIGZhbHNlKTsKCWZvciAoaW50IGkgPSAyOyBpIDwgbjsgKytpKSB7CgkJaWYgKCFpc19jb21wb3NpdGVbaV0pIHByaW1lLnB1c2hfYmFjayAoaSk7CgkJZm9yIChpbnQgaiA9IDA7IGogPCBwcmltZS5zaXplICgpICYmIGkgKiBwcmltZVtqXSA8IG47ICsraikgewoJCQlpc19jb21wb3NpdGVbaSAqIHByaW1lW2pdXSA9IHRydWU7CgkJCWlmIChpICUgcHJpbWVbal0gPT0gMCkgYnJlYWs7CgkJfQoJfQp9CiAKaW50MzJfdCBtYWluKCkgewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKG51bGxwdHIpOwogCglhdXRvIHQgPSBjbG9jaygpOwoJb2xkc2lldmUoKTsKCWF1dG8gdDEgPSBjbG9jaygpOwoJY291dCA8PCAib2xkc2lldmU6ICIgPDwgKDEuMCAqICh0MSAtIHQpKSAvIENMT0NLU19QRVJfU0VDIDw8IG5sOwoJdCA9IGNsb2NrKCk7CgluZXdzaWV2ZSgpOwoJdDEgPSBjbG9jaygpOwoJY291dCA8PCAibmV3c2lldmU6ICIgPDwgKDEuMCAqICh0MSAtIHQpKSAvIENMT0NLU19QRVJfU0VDIDw8IG5sOwp9