算法笔记——素数筛

算法笔记——素数筛

求素数是我们经常会遇到的问题，如何能提高求解素数的效率对我们解决问题至关重要，本文会记录四种求素数的方法，分别是直观算法、朴素算法，埃氏筛法和欧拉筛法

素数的定义

素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。（百度百科） 这里需要注意素数的范围是大于1的自然数，即0和1都不是素数

直观算法

直观算法是通过素数的定义来实现的，即除了1和它本身外不再有其他因素，那么我们要判断n是不是素数，只需要遍历看n是否能被2到n-1中的某个数整除即可

注：这种算法在实际判断中不会用到，这里只是为了解释素数的判断原理，实际判断某个数是否为素数推荐用下面的朴素算法

时间复杂度：O(n2)

代码实现

//从2到x-1遍历 
bool isPrime(int x)
{
	//0和1特判 
	if(x==0||x==1)
		return false;
	for(int i=2;i