关于素数判断算法优化方法的讨论

我会带着你远行 2022-08-13 03:30 121阅读 0赞

今天看见一个求给定范围内素数个数的编程题目，觉得还是有些小玄机的，特此分享一下。

所有有关素数的问题首先都会涉及到一个问题，就是判断一个数是不是素数，判断一个数是不是素数方法很简单，根据素数的定义(素数是只能被1和它自身整除的大于1的自然数)可以很容易写出程序出来，但是用一些小技巧的话可以将程序更加优化，提高算法的时间效率。

## 算法分析： ##

素数中唯一的一位偶数就是2，其余都是奇数，但也不是所有奇数都是素数，必须是只能被1和本身整除的奇数。自然而然我们会想到先特殊考虑当待测数等于2的时候，当待测数大于2的时候就从2到待测数本身遍历一遍，如果不存在能整除待测数的数，那么这个待测数就是素数。

那么就会出现两个问题。

第一个问题就是，从2开始的话，会遍历很多的偶数，但是偶数根本不需要遍历，因为大于2的偶数不可能是素数，冗余的遍历增加了算法时间复杂度；

第二个问题就是，从2一直遍历到待测数本身也是没必要的，我们可以缩小遍历范围。由数学中我们知道，如果一个数n有两个因数j和k，比如8=2\*4，2和4就是8的两个因数，假设j大于根号n，k也大于根号n，那么可以得到j\*k>根号n\*根号n>n，所以如果n能表达成j\*k，那么j和k必然有一个是小于根号n的，当我们遍历2到根号n的时候只要发现待测数存在一个不等于1和它本身的因数，那么就可以断定待测数不是素数，不存在小于根号n的因数的话也可以断定待测数就是素数，所以我们可以缩小遍历范围，从2到根号n，从而提高算法时间效率。

## 具体实现： ##

第二个问题是一定要解决的，第二个问题不解决的代码是这样的：

#include "stdafx.h"
    #include "math.h"
    //#include <ctime>
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int t=0,i=0,k=0,s=0;
    	time_t start,end;
    	do
    	{
    	//start=clock();
    	printf_s("请输入一个正数：");
    	scanf_s("%d",&t);
        if(t<=0) printf_s("输入的数不是正数！\n");
    	else if(t==2||t==3) printf_s("%d是一个素数！\n",t);
    	else if(t>3)
    	{
    		k=sqrt((float)t);
    		for(i=2;i<=k;i++)
    			if(t%i==0) 
    				{
    					printf_s("输入的数不是素数！\n");
    					s=1;
    					break;
    			    }
    		if(s!=1)
    		printf_s("%d是一个素数！\n",t);
    	}
    	else printf_s("输入的数不是素数！\n");
            s=0;
    		//end=clock();
    		//printf_s("时间为%f\n",(end-start));
            }while(1);
    	return 0;
    }

可以发现代码判断语句较为简洁，但是没有解决第一个问题，同时解决掉两个问题的代码如下：

#include "stdafx.h"
    #include "math.h"
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int t=0,i=0,k=0,s=0;
    	do
    	{
    	printf_s("请输入一个正数：");
    	scanf_s("%d",&t);
        if(t<=0) printf_s("输入的数不是正数,请重新输入！\n");
    	else if(t==2||t==3||t==5||t==7) printf_s("%d是一个素数！\n",t);
    	else if(t>9)
    	{
    		k=sqrt((float)t);
    		for(i=3;i<=k;i+=2)
    		{
    			if(t%i==0||t%2==0) 
    				{
    					printf_s("输入的数不是素数！\n");
    					s=1;
    					//break;
    			    }
    		}
    		if(s!=1) printf_s("%d是一个素数！\n",t);
    	}
    	else printf_s("输入的数不是素数！\n");
    	s=0;
    	}while(1);
    	return 0;
    }

这种方法判断语句虽然复杂了一点，但是从原理上讲是最优化的，各种算法空间复杂度差不多，我们可以通过计算程序执行的时间来判断算法时间效率，只是需要高精度的统计时间，这里不赘述，有兴趣可以补充这一议题。

参考来源：P136《C语言程序设计》杨建霑、汪同庆主编，武汉大学出版社；