1 #include
     
         //该程序为哥德巴赫猜（想输出所有的组合） 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6  7 using namespace std; 8  9 typedef unsigned long long ull;10 typedef unsigned long long LL;11 12 LL prime[6] = {
   2, 3, 5, 233, 331};13 LL qmul(LL x, LL y, LL mod) { // 乘法防止溢出， 如果p * p不爆LL的话可以直接乘； O(1)乘法或者转化成二进制加法14 //快速乘法取模算法15 16     return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod;17     /*18     LL ret = 0;19     while(y) {20         if(y & 1)21             ret = (ret + x) % mod;22         x = x * 2 % mod;23         y >>= 1;24     }25     return ret;26     */27 }28 29 LL qpow(LL a, LL n, LL mod) {30     LL ret = 1;31     while(n) {32         if(n & 1) ret = qmul(ret, a, mod);33         a = qmul(a, a, mod);34         n >>= 1;//n=n/2二进制乘除法35     }36     return ret;37 }38 39 40 bool Miller_Rabin(LL p) {41     if(p < 2) return 0;42     if(p != 2 && p % 2 == 0) return 0;43     LL s = p - 1;44     while(! (s & 1)) s >>= 1;//排除掉偶数45     for(int i = 0; i < 5; ++i) {46         if(p == prime[i]) return 1;47         LL t = s, m = qpow(prime[i], s, p);48         //二次探测定理卡米歇尔数保证该数为素数49         //卡米歇尔数若一个数为合数当0