博客

今天纠结了整整一下午的这个题，当心不静的时候，世界就更加浮躁。也许不应该这样，但是如果能时刻控制自己，那现在的我应该在家里等待笔试而不是在这里。。。

先看题：输入一个数字N，输出第N个素数的值。素数（除了1和他自己不能被其他数整除的数）

这道题有很多解法，比如暴力，N的平方的解法，但是这样的解法当数字很大的时候，其效率太差。当然对于N的平方的解法可以做一些优化，其实我们第二次只需要遍历到根号N的时候就可以了，而不用全部遍历，这样可以提高一部分效率。在此基础上，还可以，我们第二次遍历的时候有意的跳过偶数，奇数遍历到根号N的地方就好。

这些方法都可以，今天我用的方法叫什么什么算法，反正是一位希腊的大牛开发出来的，思想很简单。大体是：从2开始，将2的倍数全部标记起来，他们不是素数，然后从3开始，将3的倍数标记起来，他们也不是。然后应该到4，但是4被标记过了，所以到5，将5的倍数标记起来，，，以此类推，一直到10。然后遍历这些标记过的数据，没有标记的就是我们要求的素数。这是典型的空间换时间的算法，思路很简单。

#include <iostream>
#include <vector>
using namespace std;
#define MAX 10000

int Find_n(int n)
{
	vector<bool> ve;
	ve.resize(MAX);
	int ar[] = {2,3,5,7};
	
	int j = 0;
	for(int i = 2; i <= 10; i++)
	{
		if(i == ar[j])
		{
			int ve_i = i * 2;
			for(int k = 2; ve_i < MAX; k++)
			{
				ve[ve_i] = 1;
				ve_i = k * i;
			}
			j++;
		}
	}

//上述代码进行标记。
	int h;
	n--;
	for(h = 2; h < MAX && n; h ++)
	{
		if(!ve[h])
			n--;
	}
	if(h < MAX)
		return h-1;
	else
		return -1;
}
int main()
{
	int n;
	cin>>n;
	cout<<Find_n(n)<<endl;
}