lightoj1259

maksyuki 发表于 oj 分类，标签: 数论-素性分析

27 8月 2015

1259 - Goldbach`s Conjecture

Every even integer, greater than 2, can be expressed as the sum of two primes [1].Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:

Now your task is to check whether this conjecture holds for integers up to 10⁷.

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⁷, 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	Output for Sample Input
264	Case 1: 1Case 2: 1

Note

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

题目类型：素数筛+枚举

算法分析：使用Euler筛将素数表预先打出，然后对于每个读入的n，枚举小于等于n/2的素数，满足条件的cnt自加即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

//const int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
//const int dy[] = {-1, 1, 0, 0, -1, 1, 1, -1};
const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 10000000 + 66;

bool prime[maxn+10];
long long primelist[700000+10], prime_len;

void GetPrime ()
{
    memset (prime, true, sizeof (prime));
    prime_len = 0;

    for (long long i = 2; i <= maxn; i++)
    {
        if (prime[i])
            primelist[prime_len++] = i;

        for (long long j = 0; j < prime_len; j++)
        {
            if (i * primelist[j] > maxn)
                break;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
}

int main()
{
	GetPrime ();
//	freopen("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
	{
        printf ("Case %d: ", flag++);
		int n;
		scanf ("%d", &n);

        long long res = 0;
        for (int i = 0; i < prime_len; i++)
		{
            if (n - primelist[i] >= primelist[i] && prime[n-primelist[i]])
				res++;

			if (n - primelist[i] < primelist[i])
				break;
		}

		printf ("%lld\n", res);
	}
return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

//const int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};

//const int dy[] = {-1, 1, 0, 0, -1, 1, 1, -1};

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 10000000 + 66;

bool prime[maxn+10];

long long primelist[700000+10], prime_len;

void GetPrime ()

{

memset (prime, true, sizeof (prime));

prime_len = 0;

for (long long i = 2; i <= maxn; i++)

{

if (prime[i])

primelist[prime_len++] = i;

for (long long j = 0; j < prime_len; j++)

{

if (i * primelist[j] > maxn)

break;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

break;

}

int main()

{

GetPrime ();

// freopen("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int n;

scanf ("%d", &n);

long long res = 0;

for (int i = 0; i < prime_len; i++)

{

if (n - primelist[i] >= primelist[i] && prime[n-primelist[i]])

res++;

if (n - primelist[i] < primelist[i])

break;

}

printf ("%lld\n", res);

}

return 0;

}

lightoj1255

lightoj1266

一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

超客的水墨烟雨

lightoj1259

Input

Output

Sample Input

Output for Sample Input

Note

分类目录

标签云

书签

近期评论