判断一个数是不是素数的最快的方法（代码可以运行，Miller_Rabin + 新的）

系统管理员 2022-06-06 22:37 172阅读 0赞

## 1.自己写的（某种算法思想的改进），很快！ （只是判断一个素数，如果数据量比较大，那么会超时）    ##

#include <cstdio>
    #include <cmath>
    #include <cstring>
    int visit[100000000];
    int main()
    {
    	int n;
    	while(scanf("%d",&n)!=EOF){
    		int N  =(int) sqrt(1.0*n);
        	if(n%2==0)
       			printf("NO\n");
      		else if(n == 3||n==5 ||n==7 ||n==11 ||n==13||n==17||n==19)
    	   		printf("YES\n");
    	    else{
    	   		memset(visit,0,sizeof(visit));
    	   		for(int j=2;j<=N;j++)
    	  			visit[j] = j;
    	   		int flag = 2;
    		  	bool FF = true;
    			bool F2 = true;
    		   	for(int i=3; i<=N; )
    			{
    			  	if(n%i==0){
    			   		FF = false;
    			   		break;
    	   			}
    			        else{       // 如果除以 i 不行，那么 除以i 的倍数也不能够整除。
    					//printf(" i = %d , 剩余的等待检测的数是  ",i);
    			   		for(int j=i;j<=N;j+=i)
    			   			visit[j] = 0;   //这些数，不能再作为 因子尝试了。
    			   		for(int j=i;j<=N;j++){
    				   		if(visit[j]!=0){    //找到第一个不是 i 倍数的数
    				   			i=j;
    				   			break;
    				   		}
    						if(j == N) F2 = false;
    					}
    			   	}
    			   	if(!F2)
    			   		break;
    				/*for(int j=3;j<=N;j++)
    					printf("%d ",visit[j]);
    				printf("\n"); */
    			}
    		   	if(!FF) printf("NO\n");
    		        else printf("YES\n");
    		}
    	}
    	return 0;
    }

## 2.Miller\_Rabin 随机数判断素数的方法（应该是目前最快，把费马小定理反过来用，S越大，判断结果越正确，但是，基本上不会判错） ##

刚学习的，感觉很好用！ （无论数据量大小，都适应，很好用的！！！）

参考学习：vongang.kuangbin

/*
    费马小定理：设p 是素数，a与p互素，则 a^(p-1) ≡ 1 (mod p).
    这个定理反过来用，p 几乎一定是素数（也是成立的）
    */
    #include <cstdio>
    #include <cstdlib>
    
    const int S = 2;    //进行S次测试。 其实，2次 基本可以了。 多次更准确
    
    /*
    计算 (a*b)%c 的结果
    注意：a*b%n = (a%n * b%n) %n.
          （a+b）%n = (a%n + b%n) %n
    */
    long long mult_mod(long long a,long long b,long long c)
    {
        a = a%c;
        b = b%c;
        long long ret = 0;
        while(b){
            if(b&1){    //因为对于二进制而言，每次都是看最后一个一
                ret += a;
                ret %= c;
            }
            a = a<<1;   //因为b每次最多是1，所以把 此时 2^( a左移的次数)看作 真实算式中b的大小
            if(a>=c) a%=c;
            b = b >>1;  // b 对 2 取整
        }
        return ret;
    }
    
    /*
    解决 x^n %mod 的结果
    把 x 和 n 利用二进制进行展开，很容易求得。
    */
    long long pow_mod(long long x,long long n,long long mod)
    {
        if(n==1) return x%mod;
        x %= mod;
        long long tmp = x;
        long long ret = 1;
        while(n){
            if(n&1)
                ret = mult_mod(ret,tmp,mod); //ret = (ret *tmp) %mod
            tmp = mult_mod(tmp,tmp,mod); //tmp的每次取值是 x^1,x^2,x^4,x^8
            n = n>>1;
        }
        return ret;
    }
    /*
    二次探测定理：
    　　如果p是奇素数，则 x^2 ≡ 1(mod p)的解为 x = 1 || x = p - 1(mod p);
    */
    
    //t 是移位数。
    long long check(long long a,long long x,long long n,long long t)
    {
        long long ret = pow_mod(a,x,n);//a^x %n 快速幂取模
        long long last = ret;                           //(并且 a 与 n 互素,调用之前已经保证了 )
        for(int i=1;i<=t;i++){  //移位减掉的量补上 ! 全部补完之后是 a^(n-1) % n ，看结果是否是 1
            ret = mult_mod(ret,ret,n); //(ret*ret) % n
            if(ret ==1 && last!=1 && last!=n-1) //二次探测定理
                return true;//不是素数
            last = ret;
        }
        if(ret!=1)  //不是素数
            return true;
        return false;
    }
    /*
    　　Miller-Rabin测试：不断选取不超过n-1的基b(s次)，
    计算是否每次都有bn-1 ≡ 1(mod n)，
    若每次都成立则n是素数，否则为合数。
    */
    bool Miller_Rabin(long long n)
    {
        if(n<2) return false;
        if(n==2) return true;
        if((n&1) ==0) return false;//偶数排除
        //因为 判断公式是 x^(n-1) % n = 1 .
        //a^(n-1) ≡ 1(mod n)
        long long x = n - 1; // 求x^u % n
        long long t = 0;
        //如果 x 为偶数则x右移，用 t 记录移位数
        while((x&1) ==0){
            x = x >> 1; //右移是相除 ，结果越来越小
            t++;
        }
        for(int i=0;i<S;i++){
                //我觉得这个地方换成 n-2 比较好
            long long a = rand()%(n-1)+1;  //在 [1,n) 中 取随机数
            if(a%n ==0) continue;   //自加!!!!!!!!!!!!!!!!!!!!!!!
            if( check (a,x,n,t) )
                return false;
        }
        return true;
    }
    
    int main()
    {
        for(long long value = 1000000;value<=1000500;value++){
            if(Miller_Rabin(value))
                printf("%lld 是素数\n",value);
            else
                printf("NO\n");
        }
        return 0;
    }