华南师大 2017 年 ACM 程序设计竞赛新生初赛题解

被你们虐了千百遍的题目和 OJ 也很累的，也想要休息，所以你们别想了，行行好放过它们，我们来看题解吧。。。

A. 诡异的计数法 Description

cgy 太喜欢质数了以至于他计数也需要用质数表示！在他看来，2（第一小质数）表示1，3（第二小质数）表示2……可正因为他的计数方法太奇葩，所以他的数学成绩非常差而且拖累了他的绩点。 lxy 得知 cgy 的绩点排名之后打算告诉他，可是必须以极度麻烦的 cgy 质数计数法的方式表示。 lxy 出重金 ¥(10000000 mod 10) 请你来为他解决这个诡异的计数。

Input

输入包括多组数据，每组数据各占一行，每一行有一个正整数 n ，表示 cgy 的绩点排名，输入到文件结尾结束（ \(n \leq 100000\) ，数据组数 \(t \leq 1000000\) ）。

Output

对应每组数据输出一个质数，为 cgy 绩点排名的质数计数法。

Sample Input

1
2
28
13

Sample Output

2
3
107
41

Hint

本场比赛是网络初赛，除了不能抄袭其他选手代码外，对任何知识和资料的检索获取不作限制；

A 题并不是最简单的，题目难度不按顺序，请量力而为~

如有其他疑问请看补充说明 https://d.wps.cn/v/8pBAU

题目大意

求第 \(K\) 个质数的值

参考思路

可以选用埃氏筛法（Sieve of Eratosthenes）、欧拉筛法（Sieve of Euler）来做预处理，之后就可以直接输出。
注意先计算出第 100000 个素数是 1299709 ，所以记录数组只要开到 MaxN ，但标记数组要开到 MaxP 。
时间复杂度 \(O(NloglogN)\) 或 \(O(N)\) 。

参考代码

标程使用了埃氏筛法：

#include <stdio.h> #include <math.h> int n,cnt; int notprime[10000010]; int prime[5000010]; int main(void) { for (int i=2;i<=sqrt(10000000)+1;++i) if (!notprime[i]) for (int j=2*i;j<=10000000;j+=i) notprime[j]=1; for (int i=2;i<=10000000;++i) if (!notprime[i]) { ++cnt; prime[cnt]=i; } while (~scanf("%d",&n)) printf("%d\n",prime[n]); return 0; }