LightOJ 1259 Goldbach`s Conjecture (哥德巴赫猜想 + 素数筛选法)

http://lightoj.com/volume_showproblem.php?problem=1259

题目大意：给你一个数n，这个数能分成两个素数a、b，n = a + b且a<=b,问有几组这样的(a,b)

比较简单的哥德巴赫猜想题，不需要多说，但一般的素数判定会TLE，所以这里用的是素数筛选法

这里需要注意的是筛选出来素数数组的大小

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 1e7 +  ;

int prime[];//这里数组大小要注意，小了会RE大了会MLE

bool Isprime[N];

int k;

void Prime()

{

    k = ;

    memset(Isprime, true, sizeof(Isprime));

    Isprime[] = false;

    for(int i =  ; i < N ; i++)

    {

        if(Isprime[i])

        {

            prime[k++] = i;

            for(int j =  ; i * j < N ; j++)

                Isprime[i * j] = false;

        }

    }

}

int main()

{

    int t, n, x = ;

    scanf("%d", &t);

    Prime();

    while(t--)

    {

        x++;

        int num = ;

        scanf("%d", &n);

        for(int i =  ; i < k && prime[i] <= n /  ; i++)

        {

            if(prime[i] <= n - prime[i] && Isprime[n - prime[i]])

                num++;

        }

        printf("Case %d: %d\n", x, num);

    }

    return ;

}

LightOJ 1259 Goldbach`s Conjecture (哥德巴赫猜想 + 素数筛选法)的相关教程结束。