链接:

题意：

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.

思路：

素数表，然后暴力。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<math.h>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

const int INF = 1e9;

const int MAXN = 1e7+10;

const int MOD = 1e9+7;

bool IsPrime[MAXN];

int Prime[1000010];

int n, tot;

void Init()

{

    memset(IsPrime, 0, sizeof(IsPrime));

    IsPrime[1] = 1;

    tot = 0;

    for (int i = 2;i < MAXN;i++)

    {

        if (IsPrime[i] == 0)

            Prime[++tot] = i;

        for (int j = 1;j <= tot && i*Prime[j] < MAXN;j++)

        {

            IsPrime[i*Prime[j]] = 1;

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

                break;

        }

    }

}

int main()

{

    Init();

    int t, cnt = 0;

    scanf("%d", &t);

    while(t--)

    {

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

        scanf("%d", &n);

        int sum = 0;

        for (int i = 1;i <= tot && Prime[i] <= n/2;i++)

        {

            if (IsPrime[n-Prime[i]] == 0)

                sum++;

        }

        printf(" %d\n", sum);

    }

    return 0;

}

巴特西

LightOJ - 1259 - Goldbach`s Conjecture（整数分解定理）

链接:

题意：

思路：

代码：

最新文章

热门文章