LIGHT OJ 1259 - Goldbach`s Conjecture（素数筛选）

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## LIGHT OJ 1259 - Goldbach`s Conjecture（素数筛选）

angel_imp 2016-03-25 13:00:00 浏览1202

1259 - Goldbach`s Conjecture
 Time Limit: 2 second(s) Memory Limit: 32 MB

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

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).

# Output

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

# Note

1.      An integer is said to be prime, if it is divisible by exactly two different integers. First few primes are 2, 3, 5, 7, 11, 13, ...

My Code：

```#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 1e7+5;
const int M = 1e6+5;
typedef long long LL;
int p[M];
bool prime[MAXN];
int cnt = 0;
void isprime()
{
cnt = 0;
memset(prime, true, sizeof(prime));
prime[0] = prime[1] = false;
for(LL i=2; i<MAXN; i++)
{
if(prime[i])
{
p[cnt++] = i;
for(LL j=i*i; j<MAXN; j+=i)
prime[j] = false;
}
}
}
int main()
{
isprime();
int T,n;
scanf("%d",&T);
for(int cas=1; cas<=T; cas++)
{
scanf("%d",&n);
int sum = 0;
for(int i=0; i<cnt&&p[i]<=n; i++)
if(prime[n-p[i]])
sum++;
sum >>= 1;
if(prime[n/2])
sum++;
printf("Case %d: %d\n",cas,sum);
}
return 0;
}
```

angel_imp
+ 关注

corcosa 13170人浏览