#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 = 1e8;

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;
}