https://atcoder.jp/contests/abc280/submissions/36996709

思路：分解 $k$ 的质因数，然后枚举 $1 \sim n$，每个数乘进来就把它也分解了，然后算能不能覆盖所有 $k$ 的质因数

vector<int> o[N] o[i] 存放 $i$ 的所有质因数的 下标

#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1e6 + 10;

bitset<N> vis;
int zs[N], cnt;
int t[N], tt;
long long k, kk;
int nn;
vector<int> o[N];

int main(){
	
	for(int i = 2; i < N; i++){
		if(!vis[i]){
			zs[++cnt] = i;
			for(int j = i; j < N; j += i){
				vis[j] = 1;
				o[j].push_back(cnt);
			}
		}
	}
	
	scanf("%lld", &k);
	kk = k;
	for(int i = 1; i <= cnt && zs[i] <= k && k > 1; i++){
		while(k % zs[i] == 0){
			t[i]++;
			tt++;
			k /= zs[i];
		}
	}
	if(k > 1){
		printf("%lld\n", kk);
		return 0;
	}
	
	for(int n = 2; n < N; n++){
		nn = n;
		for(int i = 0; i < o[n].size(); i++){
			while(nn % zs[o[n][i]] == 0 && t[o[n][i]]){
				t[o[n][i]]--;
				tt--;
				nn /= zs[o[n][i]];
				if(tt == 0){
					printf("%d\n", n);
					return 0;
				}
			}
		}
	}
	
	return 0;
}