原题
题目
题目描述
输入一个正整数\(n\),求第\(n\)小的质数。
输入格式
一个不超过\(10000\)的正整数\(n\)。
输出格式
第\(n\)小的质数。
输入样例
10
输出样例
29
思路
首先打一个判断素数的函数:
bool pd(int n)//布尔值
{
if(n<2) return 0;//如果小于2,非质数
for(int i=2;i*i<=n;++i) if(n%i==0) return 0;//如果除了1和n外还有别的因数,则是合数
/*这里用了因数的成对性,只需找小因数即可*/
return 1;//是质数
}
然后模拟
上完整代码
#include<bits/stdc++.h>
using namespace std;
bool pd(int n)
{
if(n<2) return 0;
for(int i=2;i*i<=n;++i) if(n%i==0) return 0;
return 1;
}//判断素数
int main()
{
int n,i=2,s=1;//定初值
cin>>n;//读入n
while(s!=n)
{
i++;//先加一下
if(pd(i)) s++;//如果是质数,s加一
}
cout<<i;//输出第n个质数
return 0;
}