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