959D 第n小的质数大概是多少

https://codeforces.com/problemset/problem/959/D

嗯~~~

比较简单的一个问题，主要是不知道

前n个质数大概在[1,nlogn]的范围内

或者说

[1,n]的范围内有  略大于n/(logn)个质数

所以范围也确定了，再算一下复杂度，并不会爆

暴力就好了

//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//输入输出
#define PII pair<int,int>
#define PB push_back
#define x first
#define y second
using namespace std;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
typedef long long ll;
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint>
inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint>
inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(1e5+5);
set<int>S;
int n;

const int lim = 2e6;
int pr[lim];
int a[maxn];
int b[maxn];
vector<int> anal(int x)
{
	if (x == 1)return vector<int>(0);
	vector<int>ans;
	while (pr[x])
	{
		ans.PB(pr[x]);
		x /= pr[x];
	}
	ans.PB(x);
	return ans;
}
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	int T(1), times(0);
#ifdef CPP_IO// CPP_IO
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
	for (int i = 2; i*i < lim; ++i)
	{
		if (!pr[i])
		{
			for (int j = i * i; j < lim; j += i)
			{
				pr[j] = i;
			}
		}
	}
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (++times, T--)
	{
		cin >> n;
		RE2(i, n)cin >> a[i];
		for (int i = 2; i < lim; ++i)
		{
			S.insert(i);
		}

		bool fla(0);
		RE2(i, n)
		{
			if (!fla)
			{
				auto it = S.lower_bound(a[i]);
				if (*it == a[i])
				{
					b[i] = *it;
				}
				else
				{
					fla = 1;
					b[i] = *it;
				}
			}
			else
			{
				b[i] = *S.begin();
			}

			////////////////处理
			auto er = anal(b[i]);
			for (auto x : er)if (S.count(x))
			{
				for (auto j = x; j < lim; j += x)S.erase(j);
			}
		}
		RE2(i, n)
		{
			if (i != 1)cout << ' ';
			cout << b[i];
		}
		cout << ' ';
		cout << endl;

	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}