对于$a^b$，如果$b=2$，那么在$[\sqrt{n},\sqrt{n}+k\log k]$内必定能找到$k$个质数作为$a$。
筛出$n^{\frac{1}{4}}$内的所有质数，暴力枚举所有落在该区间内的倍数，将其筛掉，即可判断每个数是否是质数。
然后以最大的质数的平方作为上界，枚举更大的$a$和$b$，这里方案数指数级下降，故暴力即可。
最后排序输出第$k$小的值即可。
时间复杂度$O(n^{\frac{1}{3}}+k\log^2k)$。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1050010;
ll n,lim,t,o,b[66],q[N*2];int cnt,k,m,i,j,a[66],p[N],tot;bool v[N],vis[N*2];
inline ll pow(ll a,int b){
ll t=1;
while(b--){
if(a>lim/t)return lim+1;
t*=a;
}
return t;
}
inline ll powfast(ll a,int b){ll t=1;for(;b;b>>=1,a*=a)if(b&1)t*=a;return t;}
void sieve(ll n){
int i,j;
for(tot=0,i=2;i<=n;i++){
if(!v[i])p[tot++]=i;
for(j=0;j<tot&&i*p[j]<=n;j++){
v[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
inline void check(int x){for(ll i=max(t/x*x,2LL*x);i<=lim;i+=x)if(i>=t)vis[i-t]=1;}
int main(){
scanf("%lld%d",&n,&k);
t=max((ll)sqrt(n)-10,2LL);
while(t*t<=n)t++;
sieve((ll)sqrt(lim=t+max(k,10)*21)+5);
for(i=0;i<tot;i++)check(p[i]);
for(o=t;o<=lim&&cnt<k;o++)if(!vis[o-t])q[++cnt]=o*o;
lim=q[cnt];
for(i=3;;a[++m]=i++)if((1LL<<i)>lim)break;
for(b[1]=2;(b[1]+1)*(b[1]+1)*(b[1]+1)<=lim;b[1]++);
for(i=2;i<=m;i++)for(b[i]=b[i-1];pow(b[i],a[i])>lim;b[i]--);
sieve(max(b[1],1LL*a[m]));
for(i=1;i<=m;i++)if(!v[a[i]]){
for(j=0;j<tot&&powfast(p[j],a[i])<=n;j++);
for(;j<tot&&p[j]<=b[i];j++)q[++cnt]=powfast(p[j],a[i]);
}
sort(q+1,q+cnt+1);
return printf("%lld",q[k]),0;
}