#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() {
	int n = N;
	vector<char> is_prime(n+1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; i++) {
		if (is_prime[i] && i * i <= n) {
			for (int j = i * i; j <= n; j += i)
				is_prime[j] = false;
		}
	}
}

void newsieve(int n = N) {
	//int prime[n], is_composite[n + 1];
	std::vector <int> prime(n);
	vector<bool> is_composite(n + 1, 0);
	int cnt = 0;
	for (int i = 2; i < n; ++i) {
		if(!is_composite[i]) {
			prime[cnt++] = i;
		}
		for (int j = 0; j < cnt && i * prime[j] < n; ++j) {
			is_composite[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}

}

void newsieve1(int maxN = N) {
	int pc = 0;
	//, f[maxN], primes[maxN / 10];
	vector<int> f(maxN), primes(maxN / 10);
	for(int i = 2; i < maxN; ++i) {
		if(!f[i]) {
			primes[pc++] = i, f[i] = i;
		}
		for(int j = 0; j < pc && 1LL * i * primes[j] < maxN && primes[j] <= f[i]; ++j) {
			f[i * primes[j]] = primes[j];
		}
	}
}

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();
	newsieve1();
	t1 = clock();
	cout << "newsieve: " << (1.0 * (t1 - t)) / CLOCKS_PER_SEC << nl;
}