题目描述

输入 $n$ 输出第 $n$ 个质数。

输入格式

一个数 $n$。

输出格式

第 $n$ 个质数。

1

2

2

3

5

11

前 $8$ 个质数是：$2,3,5,7,11,13,17,19$

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 5\times 10^{7}$。

• 子任务 1（30 分）：保证 $n\le 100$。
• 子任务 2（30 分）：保证 $n=33,333,333$
• 子任务 3（40 分）：保证 $33,333,333\le n\le 33,333,333+100$

提示

• 逗号 “$,$” 只是为了方便你数数位，$33,333,333$ 就是 $33333333$
• 第 $5\times 10^7$ 个质数小于 $10^9$。