关于素数判定的算法优化

       素数的判断对于初学C语言的人来说，对循环语句的使用和算法的选择是一个非常好的锻炼。

       判断一个数是不是素数，即判断该数是否除了能被1和它本身整除外，不能被任何数整除。首先，想到的是从2开始进行除余，代码如下：

#include<stdio.h>
void main()
{
int i,j;
for(i=100;i<=200;i++)
{
for(j=2;j<i;j++)
{
if (i%j==0) 
break;
}
if(i==j)
printf("%d\n",i);
}
}

       其次，对于这个算法还可进行优化。显而易见，偶数都是非素数。 所以，可以将所有的偶数舍去，只对奇数进行判定。而除的时候用1和2也没有多少意义，1除任何数都是可以整除的，而偶数已经被舍去除2也没有意义。优化后代码如下：

#include<stdio.h>
int main()
{
	int i,j;
	for(i=101;i<=200;i=i+2)
	{
	   for(j=3;j<i;j++)
	   {
		 if(i%j==0)
	     break;
	   }
	   if(i==j)
		   printf("%6d",i);
	}
	return 0;
}

其实，这个程序优化到这一步还不是特别地好。试想，i必然是由两个数相乘而得，那么就不必从101一直除到200-1，可以直接从2到√i即可，这样大大地缩短了程序的运行时间。优化代码如下：

#include<stdio.h>
#include<math.h>

int main()
{
	int i,j,k;
	for(i=101;i<=200;i=i+2)
	
	{  
		k=sqrt(i);
        for(j=3;j<k;j++)
	   {
		 if(i%j==0)
	     break;
	   }
		 
			if(j>=k)
		   printf("%6d",i);
		 
	}
	return 0;
}

   通过对素数判定算法的优化，可以看出优化对于整个程序的时间复杂度有很大的提高，而优化对于一个程序也是至关重要的。在以后的学习中，不能拘泥于写出代码，运行没有问题就行了。而要一步一步去进行优化，使得其更加完美。

关于素数判定的算法优化

原文：http://10741665.blog.51cto.com/10731665/1698462