#P0179. 筛法(alg)

筛法(alg)

题目描述

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

  1. 写下 22nn 之间的所有整数(包括 22nn)。
  2. 找到尚未删除的最小数,并将其命名为 pp; 则 pp 是素数。
  3. 划掉 pp 及其所有尚未划掉的倍数。
  4. 如果尚有数未被划掉,请转到步骤 22

编写一个程序,给定 nnkk,找出第 kk 个被删除的整数。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

7 3

输出 #1

6

输入输出样例 #2

输入 #2

15 12

输出 #2

7

输入输出样例 #3

输入 #3

10 7

输出 #3

9

说明/提示

数据规模与约定

对于 100%100\% 的数据,有 2k<n10002 \leq k < n \leq 1000