自动搬运

查看原文

来自洛谷，原作者为

	一只大龙猫 嗷~呜！

搬运于2025-08-24 21:03:19，当前版本为作者最后更新于2021-07-04 19:55:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

由于 $n$ 最大只到 $30000$，所以我们可以从 $2$ 开始暴力枚举每一个数，看看它是不是质数。如果是，则我们只需要再找 $n-1$ 个质数就行了， $n \gets n-1$（即 C++中的n--）。如果 $n=0$，则可以跳出循环，输出现在的数，结束程序。

代码如下：

#include<iostream>
using namespace std;
int n,now=1;//now表示现在的数。 
bool check(int x){
	for(int i=2;i*i<=x;i++){//枚举到x的平方根就可以了，降低时间复杂度。 
		if(x%i==0)return 0;//若除了1和x本身还有别的因数，则x不是质数，返回0。 
	}
	return 1;//否则返回1。 
}
int main(){
	cin>>n;
	while(n!=0){ 
		now++;
		if(check(now)){
			n--; 
		}
	}
	cout<<now;
	return 0;
}

时间复杂度为 $O(n \sqrt n)$，对于这道题来说足够了。（当然还有更优的筛法，如时间复杂度仅为 $O(n)$ 的欧拉筛。想了解更多的可以看这里。）

Q&A

Q：为什么从 $2$ 而不是 $1$ 开始枚举？

A：因为 $1$ 不是质数。

Q：既然是从 $2$ 开始枚举的，那么为什么又把now初始化为 $1$？

A：因为进入循环之后，会先执行now++这条语句。到后面的判断时，now已经是 $2$ 了。