Goldbach’s conjecture is one of the oldest unsolved PRoblems in number theory and in all of mathematics. It states:
Every even integer, greater than 2, can be expressed as the sum of two primes [1].
Now your task is to check whether this conjecture holds for integers up to 107.
Input starts with an integer T (≤ 300), denoting the number of test cases.
Each case starts with a line containing an integer n (4 ≤ n ≤ 107, n is even).
For each case, print the case number and the number of ways you can express n as sum of two primes. To be more specific, we want to find the number of (a, b) where
1) Both a and b are prime 2) a + b = n 3) a ≤ b
2 6 4
Case 1: 1 Case 2: 1
先得對
判斷素數a+b=n，只要取素數a，在判斷 n-a 是否為素數即可復雜度o(φ(n))
#include<stdio.h>#include<algorithm>#define MAX_N 10000020#define P_N 664580using namespace std;bool vis[MAX_N];int p[P_N];void init(){ int cnt=0; for(int i=2;i*i<=MAX_N;i++) if(!vis[i]) for(int k=i*i;k<MAX_N;k+=i) vis[k]=true; for(int i=2;i<MAX_N;i++) if(!vis[i]) p[cnt++]=i;}int main(){ init();int T; scanf("%d",&T); for(int t=1;t<=T;t++){ int n; scanf("%d",&n); int ans=0; for(int i=0;p[i]<=n/2;i++){ if(!vis[n-p[i]]) ans++; } printf("Case %d: %d/n",t,ans); } return 0;}新聞熱點
疑難解答
