首页 > 代码库 > codevs——1530 大质数
codevs——1530 大质数
1530 大质数
时间限制: 1 s
空间限制: 1000 KB
题目等级 : 黄金 Gold
题目描述 Description
小明因为没做作业而被数学老师罚站，之后数学老师要他回家把第n个质数找出来。（1<=n<=100000)
老师随机写了几个数，交给了小明。小明百度找了很久，都没能解决。现在交给聪明的你。请你帮忙！
————————————————————————————————————————————
简单描述：把第n个质数找出来。
输入描述 Input Description
一个正整数n。
（1<=n<=100000)
输出描述 Output Description
第n个质数。
（第1个质数为2，第2个质数为3。）
样例输入 Sample Input
样例1
2
样例2
65
样例3
20133
样例输出 Sample Output
样例1
3
样例2
313
样例3
226381
数据范围及提示 Data Size & Hint
有大数据等着你，小心超时，不许交表哦。
（1<=n<=100000)
代码：
欧拉筛 暴内存。。。。
#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define N 200010using namespace std;bool not_prime[N];int n,ans,sum,tot,prime[N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f;}void Euler_sieve(){ memset(not_prime,0,sizeof(not_prime)); for(int i=2;i<=N;i++) { if(!not_prime[i]) prime[++tot]=i; for(int j=1;j<=tot;j++) { if(i*prime[j]>N) break; not_prime[i*prime[j]]=1; if(!i%prime[j]) break; } }}int main(){ n=read(); Euler_sieve();not_prime[1]=1; for(int i=1;i<=N;i++) if(!not_prime[i]) { sum++; if(sum==n) {printf("%d",i);return 0;} }}
枚举 ac。。。
注意运算符的优先级！！！
#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;int n,ans,sum,tot;int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f;}bool pd(int x){ for(int j=2;j*j<=x;j++) if(x%j==0) return false; return true;}int main(){ n=read();tot=1;ans=2; for(int i=3;tot<n;i+=2) if(pd(i)) ans=i,tot++; printf("%d",ans); return 0;}
codevs——1530 大质数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。