【寒假每日一题】洛谷 P6421 [COCI2008-2009#2] RESETO
题目链接：P6421 [COCI2008-2009#2] RESETO - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
埃拉托色尼筛法是一种著名的素数筛法，可以查找所有直至 n 的素数。该算法的步骤是：
1. 写下 2 到 n 之间的所有整数（包括 2 和 n）。
2. 找到尚未删除的最小数，并将其命名为 p； 则 p 是素数。
3. 划掉 p 及其所有尚未划掉的倍数。
4. 如果尚有数未被划掉，请转到步骤 2。
编写一个程序，给定 n 和 k，找出第 k 个被删除的整数。
输入格式
一行两个整数 n 和 k，其具体含义请见题目描述。
输出格式
一行一个整数，表示第 k 个被划掉的整数。
样例 #1
样例输入 #1
7 3样例输出 #1
6样例 #2
样例输入 #2
15 12样例输出 #2
7样例 #3
样例输入 #3
10 7样例输出 #3
9提示
数据规模与约定
对于 100% 的数据，有 2 <= k < n <= 1000。
说明
题目译自 COCI2008-2009 CONTEST #2 RESETO，译者 @mnesia。
附件下载
contest2_tasks.pdf 101.88KB
AC code:
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int a[n + 1];
int cnt = 0;
for(int i = 0 ; i <= n ; i ++)
a[i] = 1;
for(int i = 2 ; i <= n ; i ++)
{
for(int j = i ; j <= n ; j ++)
{
if(j % i == 0 && a[j] == 1)
{
a[j] = 0;
cnt ++;
if(cnt == k)
{
cout<<j<<endl;
return 0;
}
}
}
}
return 0;
}