39:第n小的质数
总时间限制: 1000ms 内存限制: 65536kB
描述
输入一个正整数n，求第n小的质数。
输入
一个不超过10000的正整数n。
输出
第n小的质数。
样例输入
10
样例输出
29
方法一：老实枚举计数寻找到第n个质数然后输出。
1 #include<stdio.h> 2 #include<math.h> 3 int main(int argc, char *argv[]) 4 { 5 long i,n,count; 6 long j,flag,t; 7 scanf("%d",&n); //需要寻找第n个质数 8 count=0; //已经寻找到count个 9 10 i=2; 11 //i从2开始逐渐增大。依次判断i的值是否是质数并计数 12 while(count<n) 13 { 14 //判断i是否质数 15 j=2;flag=0;t=sqrt(i); 16 while(j<=t) 17 { 18 if(i%j==0) 19 { 20 flag=1; 21 break; 22 } 23 j++; 24 } 25 //如果i是质数，count计数器加1 26 if(flag==0) count++; 27 i++;//准备判断下一个数 28 } 29 printf("%d\n",i-1); 30 return 0; 31 }
方法二：离线计算，先打印出10000质数存到数组中，然后……呵呵
把上面的代码稍微修改一下，用来生成质数并输出到文件里面：
1 #include<stdio.h> 2 #include<math.h> 3 int main(int argc, char *argv[]) 4 { 5 long i,n,count; 6 long j,flag,t; 7 freopen("39.out","w",stdout); 8 //scanf("%d",&n); //需要寻找第n个质数 9 n=10003; 10 count=0; //已经寻找到count个 11 12 i=2; 13 //i从2开始逐渐增大。依次判断i的值是否是质数并计数 14 while(count<n) 15 { 16 //判断i是否质数 17 j=2;flag=0;t=sqrt(i); 18 while(j<=t) 19 { 20 if(i%j==0) 21 { 22 flag=1; 23 break; 24 } 25 j++; 26 } 27 //如果i是质数，count计数器加1 28 if(flag==0) 29 { 30 count++; 31 printf("%d,",i); 32 } 33 i++;//准备判断下一个数 34 } 35 //printf("%d\n",i-1); 36 return 0; 37 }
然后复制文件当中的数据到代码里面构造数组嘿嘿嘿
1 #include <stdio.h> 2 int main(int argc, char *argv[]) 3 { 4 long a[10003]= 5 { //为了网页打开速度快一点，不写完数据了呵呵 6 2,3,5,7,11,13,17,19,23,29,31,…… 7 }; 8 int n; 9 scanf("%d",&n); 10 printf("%d\n",a[n-1]); 11 return 0; 12 }
嗯，投机取巧了呵呵
