当前位置: 首页 > news >正文

【寒假每日一题】洛谷 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;
} 

相关文章:

  • aws codesuit 在codebuild和codepipeline中集成jenkins
  • DPU网络开发SDK—DPDK(八)
  • DW 2023年1月Free Excel 第五次打卡 文本函数
  • 第四层:友元与函数成员别样定义
  • SpringCloud(11):Hystrix请求合并
  • SpringBoot的自动配置
  • C语言萌新如何使用scanf函数?
  • TryHackMe-NahamStore(常见web漏洞 大杂烩)
  • 【Java入门】Java数据类型
  • Spring三级缓存
  • 【每日一道智力题】之 轮流取石子(尼姆博弈的详解)
  • linux——高级信号