首页 > 代码库 > 九度OJ 1040 Prime Number (筛素数,试除法)
九度OJ 1040 Prime Number (筛素数,试除法)
- 题目描述:
Output the k-th prime number.
- 输入:
k≤10000
- 输出:
The k-th prime number.
- 样例输入:
3 7
- 样例输出:
5 17
#include<stdio.h> int k[10001]; int main(int argc, char *argv[]) { k[1]=2; int index=1; int i,j; int num; int tmp; while(scanf("%d",&num)!=EOF) { if(index>=num) printf("%d\n",k[num]); else { for(i=index+1;i<=num;++i) { tmp=k[i-1]+1; while(1){ for(j=1;j<=index;++j) { if(tmp%k[j]==0) break; } if(j<=index) tmp++; else { k[i]=tmp; index++; break; } } } printf("%d\n",k[num]); } } return 0; }今天本来想用筛选法做的,可是老错老错,后来才发现致命错误!!!(查了下,第10000个素数是接近30000的一个数,而我的筛选数组才10000大小。。。)
#include<iostream> #include<string.h> #include<stdio.h> using namespace std; #define M 1000010 bool flag[M]; int prime[M]; void getprime() { int cnt=1; for(int i=2;i<M;++i) { if(!flag[i]) { prime[cnt++]=i; for(int j=i;j<M;j+=i) flag[j]=true; } } } int main(int argc, char *argv[]) { int k; // freopen("1040.in","r",stdin); getprime(); prime[0]=0; while(scanf("%d",&k)!=EOF) { printf("%d\n",prime[k]); } return 0; }
更喜欢筛选法,简单明了,而且还快
对比下测试结果——
试选法:
筛选法:
九度OJ 1040 Prime Number (筛素数,试除法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。