题意
一句话题意,就是问不含小于等于n的素数因子的第k大合数。(n,k<=1000)
(样例解释中的189应该是11 * 17=187,在此更正一下,但是不影响做这道题。)
分析
读懂题目之后,不含小于等于n的素数因子,意思就是只含有大于n的素数因子的合数,我们要找第k个。
然后因为没有什么好思路,所以我们先确定一下本题答案的上界,也就是n等于1000,k等于1000的时候,这个数大约在什么范围。
而最小的大于1000的素数因子可以找到是1009,合数最小包含两个素数因子,暂时先假设另一个所含素数因子为p1,因此找到的合数便可以表示成 1009* p1。
因为k最大是1000,所以我们暴力的想,p1是大于1000的第1000个素数,此时的p1不过1e4左右,这其实确定出来的合数才大约1e7而已,而实际找到的第k个数要远远小于该合数。至于包含三个以及三个以上素数因子的情况,乘起来最少也要1e9,因此在确定最大数的时候无需考虑。
这时候当我们确定了最大的数也不超过1e7的时候,就可以大胆的暴力做了,打出1e7的素数表,然后用小于n的素数筛一下是否满足题意,暴力找就可以了。复杂度大约是2e6*log。
总结一下,这题就实际上根据数据范围确定最大数的边界,然后得到勇气之后暴力解题。
欧拉筛法不会的同学建议百度自学。
推荐 https://oi-wiki.org/math/sieve/
最后贴一下AC代码。
代码
#pragma GCC optimize(3)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pp;
const int N=1e7+5;
const int tmp=31;
const int mod=1e6+7;
const double eps=1e-8;
const double pi=acos(-1);
int p[N/5],cnt;
bool vis[N];
void erla()
{
int n=N-5;
vis[0]=vis[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i])p[++cnt]=i;
for(int j=1;j<=cnt&&p[j]*i<=n;j++){
vis[p[j]*i]=1;
if(i%p[j]==0)break;
}
}
}
int main()
{
erla();
int n,k;
scanf("%d%d",&n,&k);
for(int i=n+1;;i++){
if(!vis[i])continue;
int f=0;
for(int j=1;p[j]<=n;j++){
if(i%p[j]==0){
f=1;
break;
}
}
if(!f)k--;
if(k==0){
printf("%d\n",i);
return 0;
}
}
return 0;
}