第n小的质数

2019-03-08

view times

描述
输入一个正整数n，求第n小的质数。
输入
一个不超过10000的正整数n。
输出
第n小的质数。

样例输入

10

样例输出

29

方法一
判断一个数n是不是素数，可以用2到$\sqrt{n}$之间的所有整数去除n，看能否整除，如果都不能则n是质数

#include <stdio.h>
#include <stdlib.h>
#include <math.h>s

int main(int argc, char *argv[]) {
	int n;
	int m=1,i,t=2,f;
	scanf("%d",&n);
	if(n==1)
		printf("2");
	else{
	
		while(t<=n){
			f=1;
			m+=2;    //偶数不是质数，步长可以加大 
			for(i=3;i<=sqrt(m);i=i+2){   //m是奇数，当然不能被偶数整除，步长也可以加大。
				if(m%i==0){
				  f=0;
				  break;
				}
			}
			
			if(i>sqrt(m))
			 t++;
			 
	    }
	    printf("%d",m);
	}
	return 0;
}

方法二
筛选法求质数：把2到n中所有的数都列出来，然后从2开始，先划掉n内所有2的倍数，然后每一次从下一个剩下的数（必然是素数）开始，划掉其n内的所有倍数。最后剩下的数，都是素数。
以空间换时间，加快了计算速度

#include <iostream>
#include <string>
#include <cmath> 
#include <fstream>
using namespace std;

#define MAX_NUM 1000000
bool isPrime[MAX_NUM+10];  //值为1表示i为素数 
 
int main(int argc, char** argv) {
	int n;
	cin>>n;
	for(int i=2;i<=MAX_NUM;i++)
		isPrime[i]=true;   //开始假设所有数都是素数 
	
	for(int i=2;i<=MAX_NUM;i++){   //每一次将一个素数的所有倍数标记为非素数 
		if(isPrime[i]){			   //仅标记素数的倍数 
			for(int j=2*i;j<=MAX_NUM;j+=i)
				isPrime[j]=false;	//将素数i的倍数标记为非素数 
		}
	}
	int c=0;
	for(int i=2;i<=MAX_NUM;i++){
		if(isPrime[i])
			c++;
		if(c==n){
	
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}