题解 P6421 【[COCI2008-2009#2] RESETO】

· · 题解

思路：

按照题目说的模拟，我在这里手动模拟一下。

设 n 为 7 , k 为6。

写下2,3,4,5,6,7

第一轮，找到第一个素数 2,划掉，成为：3,4,5,6,7

第二轮划掉 2 的倍数，成为：3,5,6,7

第三轮，继续划掉 2 的倍数，成为：3,5,7

第四轮， 3 没有被划掉，划掉，成为：5,7

第五轮， 5 没有被划掉，划掉，成为：7

第六轮，只剩下 7，输出7

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    bool s[1001];//来存下这些数
    int n,k,w=0;//w记录划掉了几个数
    cin>>n>>k;//输入
    memset(s,true,sizeof(s));//写下所有数
    for(int i=2;i<=n;i++)//找没有划掉的数
    {
        if(s[i]==true)//如果没有被划掉
        {
            for(int j=i;j<=n;j+=i)//找它的倍数
            {
                if(s[j]==true)//如果它的倍数没被划掉
                {
                    w++;//又划掉一个数
                    s[j]=false;//现在它被划掉了
                    if(w==k)//如果已经划掉k个数
                    {
                        cout<<j;//输出答案
                        return 0;//结束
                    }
                }
            }
        }
    }
    return 0;//别忘了
}

谢谢观赏！