素数判定Miller_Rabin 算法详解
例如：
Goldbach
#include<bits/stdc++.h>
using namespace std;
unsigned long long n;
const int times = 5;
int number = 0;unsigned long long Random( unsigned long long n ) //生成[ 0 , n ]的随机数
{return ((double)rand( ) / RAND_MAX*n + 0.5);
}unsigned long long q_mul( unsigned long long a, unsigned long long b, unsigned long long mod ) //快速计算 (a*b) % mod
{unsigned long long ans = 0;while(b){if(b & 1){b--;ans =(ans+ a)%mod;}b /= 2;a = (a + a) % mod;}return ans;
}unsigned long long q_pow( unsigned long long a, unsigned long long b, unsigned long long mod ) //快速计算 (a^b) % mod
{unsigned 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( unsigned long long a, unsigned long long n )//miller_rabin算法的精华
{//用检验算子a来检验n是不是素数unsigned long long tem = n - 1;int j = 0;while(tem % 2 == 0){tem /= 2;j++;}//将n-1拆分为a^r * sunsigned long long x = q_pow( a, tem, n ); //得到a^r mod nif(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( unsigned 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次随机检验{unsigned long long a = Random( n - 2 ) + 1; //得到随机检验算子 aif(!witness( a, n )) //用a检验n是否是素数return false;}return true;
}
int main(){int T;scanf("%d",&T);while(T--){int a,b,c;char ch;cin>>n;if(n==2){cout<<1<<" "<<1<<endl;}else if(n==4){cout<<1<<" "<<3<<endl;}else{for(int i=3;i<=(n/2);i+=2){if(miller_rabin( i )&&miller_rabin( n-i )){cout<<i<<" "<<n-i<<endl;break;}}}}return 0;
}