欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

筛法求素数

程序员文章站 2024-03-15 13:06:29
...

判断素数的方法很简单:

 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