39:第n小的质数

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
",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
",i-1);
36     return 0;
37 }

View Code

然后复制文件当中的数据到代码里面构造数组嘿嘿嘿

 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
",a[n-1]);
11     return 0;
12 }

嗯，投机取巧了呵呵