P1216 埃拉托色尼筛法

入门 传统题 GESP线性筛 上传者
时间限制2000ms
内存限制50MiB
通过 / 提交0/0

P1216埃拉托色尼筛法

入门 传统题 GESP线性筛 上传者
时间限制2000ms
内存限制50MiB
通过 / 提交0/0

题目描述

埃拉托色尼筛法是一种著名的素数筛法,可以查找所有直至 n 的素数。该算法的步骤是:

1.写下 2 到 n 之间的所有整数(包括 2 和 n)。

2.找到尚未删除的最小数,并将其命名为 p; 则 p 是素数。

3.划掉 p 及其所有尚未划掉的倍数。

4.如果尚有数未被划掉,请转到步骤 2。

编写一个程序,给定 n 和 k,找出第 k 个被删除的整数。

输入格式

一行两个整数 n 和 k,其具体含义请见题目描述。

输出格式

一行一个整数,表示第 k 个被划掉的整数。

样例输入1

7 3

样例输出1

6

样例输入2

15 12

样例输出2

7

数据范围

2以上1000以内