題目鏈接：點擊查看

題目大意：給出一個偶數，將其拆為兩個素數之和

題目分析：因為將一個偶數拆為兩個素數和時，答案會有多種情況，挑較小的素數最小時，一般此素數會非常小，最大也超不過一萬，所以我們需要解決如何快速判斷一個數是否為素數，如果用素數的定義來判斷，那么根號n的時間復雜度隨便一個long long都會吃不消，所以我們用到了米勒羅賓素數測試，直接套一個模板，記得用unsigned long long，因為即便是long long，加一下也可能會爆掉，然后就是板子題了，借助這個題學了一波新方法來測試素數

上代碼：

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef unsigned long long LL;//懶得改模板了，就直接把這里改了-.-const int inf=0x3f3f3f3f;const int N=1e6+100;LL prime[6]={2,3,5,233,331}; LL qmul(LL a, LL b, LL mod)//快速乘防止爆long long { LL ans=0; while(b) { if(b&1) ans=(ans+a)%mod; a=a*2%mod; b>>=1; } return ans; } LL qpow(LL a, LL b, LL mod) { LL ans=1; while(b){ if(b&1) ans=qmul(ans,a,mod); a=qmul(a,a,mod); b>>=1; } return ans; } bool Miller_Rabin(LL p) { if(p<2) return false; if(p!=2&&p%2==0)return false; LL s=p-1; while(!(s&1))s>>=1; for(int i=0;i<5;++i) { if(p==prime[i]) return 1; LL t=s,m=qpow(prime[i],s,p); while(t!=p-1&&m!=1&&m!=p-1) { m=qmul(m,m,p); t<<=1; } if(m!=p-1&&!(t&1)) return false; } return true; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){LL n;cin>>n;for(LL i=2;i<n;i++)if(Miller_Rabin(i)&&Miller_Rabin(n-i)){printf("%llu %llu\n",i,n-i);break;}}return 0; }

?

總結

以上是生活随笔為你收集整理的2018宁夏邀请赛 - Goldbach(米勒罗宾素数测试)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。