算法记录——快速判定多个数（1~1e18）是否为质数（Miller_rabin）

妖狐艹你老母 2022-12-19 11:51 8阅读 0赞

#### [质数判定][Link 1] ####

题目描述  
判定输入的数是不是质数。

输入格式  
若干行，一行一个数 。  
行数不超过 105。  
输出格式  
对于输入的每一行，如果 是质数输出一行 Y，否则输出一行 N。

样例  
样例输入  
1  
2  
6  
9  
666623333  
样例输出  
N  
Y  
N  
N  
Y

数据范围与提示  
1 <= x <= 1 \* 1018

欢迎hack（如果你不是管理员，可以在题目讨论区发帖）。

--------------------

#### [Miller\_rabin 详解链接][Miller_rabin] ####

**Miller\_rabin算法**  
优势可以单独判断一个大数是否素数。  
缺点他是一个不保证正确的算法，我们只能通过多次执行算法让这个错误的概率很小，不过幸运的是通常来看它的错误概率可以小到忽略不计。

#include <iostream> 
    #include <cstdio> 
    #include <algorithm> 
    #include <cmath> 
    #include <cstring> 
    #include <map> 
    using namespace std;
     
    const int times = 13;
    int number = 0;
     
    map<long long, int>m;
    long long Random( long long n )			//生成[ 0 , n ]的随机数
    { 
    	return ((double)rand( ) / RAND_MAX*n + 0.5);
    }
     
    long long q_mul( long long a, long long b, long long mod ) //快速计算 (a*b) % mod
    { 
    	long long ans = 0;
    	while(b)
    	{ 
    		if(b & 1)
    		{ 
    			b--;
    			ans =(ans+ a)%mod;
    		}
    		b /= 2;
    		a = (a + a) % mod;
     
    	}
    	return ans;
    }
     
    long long q_pow( long long a, long long b, long long mod ) //快速计算 (a^b) % mod
    { 
    	long long ans = 1;
    	while(b)
    	{ 
    		if(b & 1)
    		{ 
    			ans = q_mul( ans, a, mod );
    		}
    		b /= 2;
    		a = q_mul( a, a, mod );
    	}
    	return ans;
    }
     
    bool witness( long long a, long long n )//miller_rabin算法的精华
    { //用检验算子a来检验n是不是素数
    	long long tem = n - 1;
    	int j = 0;
    	while(tem % 2 == 0)
    	{ 
    		tem /= 2;
    		j++;
    	}
    	//将n-1拆分为a^r * s
     
    	long long x = q_pow( a, tem, n ); //得到a^r mod n
    	if(x == 1 || x == n - 1) return true;	//余数为1则为素数
    	while(j--) //否则试验条件2看是否有满足的 j
    	{ 
    		x = q_mul( x, x, n );
    		if(x == n - 1) return true;
    	}
    	return false;
    }
     
    bool miller_rabin( long long n )  //检验n是否是素数
    { 
     
    	if(n == 2)
    		return true;
    	if(n < 2 || n % 2 == 0)
    		return false;				//如果是2则是素数，如果<2或者是>2的偶数则不是素数
     
    	for(int i = 1; i <= times; i++)  //做times次随机检验
    	{ 
    		long long a = Random( n - 2 ) + 1; //得到随机检验算子 a
    		if(!witness( a, n ))						//用a检验n是否是素数
    			return false;
    	}
    	return true;
    }
     
     
    int main( )
    { 
    	long long tar;
    	while(cin >> tar)
    	{ 
    		if(miller_rabin( tar ))	//检验tar是不是素数
    			cout << "Y" << endl;
    		else
    			cout << "N" << endl;
    	}
    	return 0;
    }

[Link 1]: https://loj.ac/problem/143
[Miller_rabin]: https://blog.csdn.net/maxichu/article/details/45458569?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160471831319725255532793%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160471831319725255532793&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-45458569.pc_first_rank_v2_rank_v28p&utm_term=Miller_Rabin&spm=1018.2118.3001.4449