哥德巴赫猜想

哥德巴赫猜想:任何一个大于2的偶数,都可以表示为两个素数之和。
另外还有,任何一个大于5的奇数都可以表示为三个素数之和。
给定一个正整数n,范围是[2,10^9],把n表示为若干个素数的和,输出一种方案,使得素数的个数最少。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>

using namespace std;
typedef long long LL;
const int N = 10005;
const LL MOD = 1000000007;

bool prime[N];
int p[N];
int k;

vector<LL> v1;
vector<LL> v2;
vector<LL> *p1;
vector<LL> *p2;

void isprime()
{
    k = 0;
    int i,j;
    memset(prime,true,sizeof(prime));
    for(i=2;i<N;i++)
    {
        if(prime[i])
        {
            p[k++] = i;
            for(j=i+i;j<N;j+=i)
            {
                prime[j] = false;
            }
        }
    }
}

void Work()
{
    p1 = &v1;
    p2 = &v2;
    for(int i=0;i<N;i++)
    {
        if(i&1) p1->push_back(0);
        else    p1->push_back(1);
    }
    for(int i=1;i<k;i++)
    {
        p2->clear();
        for(int j=0;j<N;j++)
        {
            if(j < p[i]) p2->push_back((*p1)[j]%MOD);
            else         p2->push_back(((*p1)[j]%MOD + (*p2)[j-p[i]]%MOD)%MOD);
        }
        vector<LL> *tmp;
        tmp = p2;
        p2 = p1;
        p1 = tmp;
    }
}

int main()
{
    int n;
    isprime();
    Work();
    while(cin>>n)
    {
        cout<<(*p1)[n]<<endl;
    }
    return 0;
}

如果哥德巴赫猜想是正确的,一个(不小于6的)偶数,都是两个素数之和。那么这个偶数能被至少一个素数对表示,如14,即可以表示为14=3+11,也可以表示为14=7+7。不同的偶数对应的素数对的数目是不一样的,如偶数6,就只能表示为6=3+3。对于每个给定的偶数,我们希望知道有多少素数对的和等于该偶数。

#include <iostream>
#include <math.h>
#define maxn 16777220
using namespace std;
bool a[maxn];
int main()
{
    int n;
    for(int i=0;i<=maxn;i++)
    a[i]=1;
    for(int i=2;i<=sqrt(maxn);i++)
    if(a[i])
    for(int k=i*2;k<=maxn;k+=i)
    a[k]=0;
    while(cin>>n)
    {
        int s=0;
        for(int i=3;i<=n/2;i++)
        if(a[i]&&a[n-i])
        {
            s++;
        }
        cout<<s<<endl;
    }return 0;
}
0

Leave a Reply

Your email address will not be published.