日期:2014-05-16  浏览次数:20437 次

Goldbach's Conjecture map+素数表
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
const int maxn=1000001;
map <int,int> mp;
int p[maxn];
bool vis[maxn];
int t,n;
void get_prime()
{
    memset(vis,false,sizeof(vis));
    memset(p,0,sizeof(p));
    t=0;
    for(int i=2; i<=maxn; i++)
    {
        {
            for(int j=i*2; j<=maxn; j+=i)
                vis[j]=true;
        }
        if(!vis[i]) p[t]=i,mp[i]=t,t++;
    }
}
int main()
{
    get_prime();
    while(scanf("%d",&n)==1&&n)
    {
        bool fuck=false;
        int ans=0;
        for(int i=0; i<t; i++)
        {
            ans=n-p[i];
            if(mp[ans]!=0)
            {
                fuck=true;
                break;
            }
        }
        if(!fuck) printf("Goldbach's conjecture is wrong.\n");
        else printf("%d = %d + %d\n",n,n-ans,ans);
    }
    return 0;
}