筛法求素数

判断素数的方法很简单：

 1 int is_yes(int x)
 2 {
 3     if (x == 1 || x == 2)
 4         return 1;
 5     for (int i = 2; i <= srqt(x); i++)
 6     {
 7         if (x%i == 0)
 8             return 0;
 9     }
10     return 1;
11 }

然而有很多数的时候 ，很显然，如果从头选到尾，是非常耗费时间的。

所以用这个方法写的时候就显出了优势，就是省时。

先从小到大排序，把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

int a[mxan];
void is_yes()
{
	memset(a, 0, sizeof(a));
	a[1] = 1;
	for (int i = 2; i <= sqrt(n); i++)
	{
		if (a[i] == 0)//如果i是素数
		{
			for (int j = 2; i*j < n; j++)
			{
				a[i*j] = 1;//那么i*j肯定不是素数
			}
		}
	}
}
//所有的非素数标记为1，素数都标记为0

　　

素数：只有1和自身两个约数的正整数.

一般通过定义来进行判断的话，可以直接来判断一个数字是否为素数。但是期复杂度是O（n*sqrt(n)）。很显然，这个的效率非常低。

-------------------------------下面是一种较为高效的算法------------------------------------

具体的实现：将1-n个自然数一次排序。1不是质数也不是合数，要划去。第二个数是2，2是质数留下来，而把2后面能被2整除的所有整数都划去。2后面的3没有划去，3是质数，把3留下，再把3后面的所有能被3整除的数划去，以此类推，，，每次都把没有去掉的数的后面的能被该数整除的数都划去。然后将没划去的数记录下来。

 

算法实现：

 1 #define Max 1000000
 2 int prime[Max];
 3 
 4 void Isprime()
 5 {
 6     int n,i,j,k=1;
 7     
 8     memset(prime,0,sizeof(prime));
 9     for(i=2;i<Max;i++)
10     {
11         if(!prime[i])
12         {
13             prime[i]=k++;
14             for(j=i+i;j<Max;j+=i)
15                 prime[j]=prime[i];
16         }
17     }
18 } 

 其实还有其他好几种方法，可能更高效，参加下面大佬的博客：

http://blog.csdn.net/dinosoft/article/details/5829550