題目大意：求講一個整數n分解為兩個素數的方案數。

題目思路：素數打表，后遍歷 1-n/2，尋找方案數，需要注意的是：C/C++中 bool類型占用一個字節，int類型占用4個字節，在素數打表中采用bool類型可以節約不少內存。

?

#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<stdio.h> #include<queue> #include<math.h> #define INF 0x3f3f3f3f #define MAX 10000005 #define Temp 10000005using namespace std;int p[664589],cnt=0; bool vis[MAX];void GetPrime()//素數打表 {memset(vis,false,sizeof(vis));memset(p,0,sizeof(p));for(int i=2;i<MAX;i++){if(!vis[i]){p[++cnt]=i;for(int j=i+i;j<MAX;j+=i){vis[j]=true;}}} }int main() {GetPrime();int n,T,sum,cns=0;scanf("%d",&T);while(T--){sum=0;scanf("%d",&n);for(int i=1;p[i]<=n/2;i++)//遍歷尋找方案數 {if(vis[n-p[i]]==false)sum++;}printf("Case %d: %d\n",++cns,sum);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/alan-W/p/5908811.html

總結

以上是生活随笔為你收集整理的LightOJ 1259 Goldbach`s Conjecture 素数打表的全部內容，希望文章能夠幫你解決所遇到的問題。

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