素数的高效算法

水深无声 2022-04-24 07:36 254阅读 0赞

素数最简单的判断方法是采用枚举，复杂度为O（n）。（这里不作解释）

这里将介绍下列几点：  
1）素数判断，复杂度为O（√n）的原理及代码。  
2）素数表的获取。  
3）更为高效判断素数的"筛选法"。

**（一）素数判断**  
这里介绍复杂度为O（√n）的原理：  
例：2~n-1中存在n的约数，不妨设为k，即n%k==0，那么由k\*（n/k）==0，n/k也是n的一个约数，因此得到了k与n/k中一定满足：一个数小于√n，一个数大于√n。  
这里稍作解释：√n\*√n=n，而k\*n/k=n，因此一个约数小于√n，一个约数大于√n。  
启示：只需判断n能否被2，3...，|\_√n\_|中的一个整除即可（其中|\_√n\_|表示向下取整）。

在此注意sqrt()函数的用法：  
1）传入的参数应为浮点型。  
2）返回的类型也为浮点型。

因此：请严格按照标准来书写代码。

bool isPrime(int n){
    	if(n<=1) return false;
    	int sqr=(int)sqrt(1.0*n);
    	for(int i=2;i<=sqr;i++){
    		if(n%i==0) return false;
    	}
    	return true;
    }

可能你还有看到其他更为简单的写法如：

bool isPrime(int n){
    	if(n<=1) return false;
    	for(int i=2;i*i<=n;i++){
    		if(n%i==0) return false;
    	}
    	return true;
    }

建议新手不要使用此简单的写法，原因：在n接近int类型范围上界时，i\*i极有可能越界溢出。（当然n在10^9以内是绝对安全的）  
不过这也是有解决办法的：将i定义为long long类型即可。

**（二）获取表**  
方法：从1~n枚举，判断每个数是否为素数。  
时间复杂度：一部分O（n），另一部分O（n√n），因此获取表的复杂度为O（n\*n√n）。

#include <stdio.h>
    #include <math.h>
    
    //求100以内素数表 
    bool isPrime(int );
    int prime[101],Num=0;
    void Find_Prime(){
    	for(int i=1;i<101;i++){
    		if(isPrime(i)==true){
    			prime[Num++]=i;
    		}
    	}
    }
    
    //判断n是否为素数 
    bool isPrime(int n){
    	if(n<=1) return false;
    	int sqr=(int)sqrt(1.0*n);
    	for(int i=2;i<=sqr;i++){
    		if(n%i==0) return false;
    	}
    	return true;
    }
    int main(){
    	Find_Prime();
    	for(int i=0;i<Num;i++) {
    		printf("%d ",prime[i]);
    	}
    	return 0;
    }

**（三）筛选法求素数**  
原理：把2到n中所有的数都列出来，然后从2开始，先划掉n内所有2的倍数，然后每次从下一个剩下的数（必然是素数）开始，划掉其n内的所有倍数。最后剩下的数，就都是素数。

具体过程：自己百度。

int prime[101],Num=0;
    bool p[101]={0};//如何为素数则为false 
    void Find_Prime(){
    	for(int i=2;i<101;i++){
    		if(p[i]==false){
    			prime[Num++]=i;
    			for(int j=i+i;j<101;j=j+i){
    				p[j]=true;
    			}
    		}
    	}
    }

时间复杂度为O(nloglogn)