判断素数的方法很简单:
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