Goldbach`s Conjecture 【素数线性筛法】

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/44163723

Goldbach`s Conjecture

Time Limit: 2000 MS Memory Limit: 32768 KB 64bit IO Format: %lld & %llu

Submit Status

Description

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 **10 7 ** .

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 ≤ 10 7 , 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

Sample Input

2

6

4

Sample Output

Case 1: 1

Case 2: 1

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <ctype.h>
#include <time.h>
#include <queue>
#include <iterator>

using namespace std;

int t;
const int MAXN = 10000010;

bool com[MAXN];
int primes, prime[MAXN/10];//数组不必开的太大

void solve(int n)
{
	primes = 0;
	memset(com,false,sizeof(com));
	com[0] = com[1] = true;
	for (int i = 2; i <= n; ++i)
	{
		if (!com[i])
		{
			prime[++primes] = i;
		}
		for (int j = 1; j <= primes && i*prime[j] <= n; ++j)
		{
			com[i*prime[j]] = true;
			if (!(i % prime[j]))
				break;
		}
	}
}

int main()
{
	solve(10000000);
	int t, cases = 1, n;
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d", &n);
		
		
		int ans = 0;
		for (int i = 1; prime[i] * 2 <= n; i++)//效率高
		{
			if (!com[n - prime[i]])
				ans++;
		}
		printf("Case %d: %d\n", cases++, ans);
	}
	return 0;
}