POJ 2262 哥德巴赫猜想

题目详情

解法：欧拉筛法的基本应用

模板：欧拉筛法

#define MAXN 50005

bool u[MAXN];  //辅助数组做筛子
int su[MAXN]; //素数集合

void SieveofEuler(int n)
{
    int i,j,num=0;
    memset(u,true,sizeof(u));
    for(i=2;i<=n;i++)
    {
        if(u[i])
        {
            su[num++]=i;
        }
        for(j=0;j<=num;j++)
        {
            if(i*su[j]>n)
            {
                break;
            }
            u[i*su[j]]=false;
            if(i%su[j]==0)
            {
                break;
            }
        }
    }
}

题解代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define MAXN 1000050

using namespace std;

bool u[MAXN];  //辅助数组做筛子
int su[MAXN]; //素数集合

void SieveofEuler(int n)
{
    int i,j,num=0;
    memset(u,true,sizeof(u));
    for(i=2;i<=n;i++)
    {
        if(u[i])
        {
            su[num++]=i;
        }
        for(j=0;j<=num;j++)
        {
            if(i*su[j]>n)
            {
                break;
            }
            u[i*su[j]]=false;
            if(i%su[j]==0)
            {
                break;
            }
        }
    }
}

int main()
{
    SieveofEuler(1000050);
    int n;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
        bool ok=false;
        int i;
        for(i=0;i<=n;i++)
        {
            if(su[i]*2>n)
            {
                break;
            }
            if(u[n-su[i]])
            {
                ok = true;
                break;
            }
        }
        if(!ok)
        {
            puts("Goldbach's conjecture is wrong.");
        }
        else{
            printf("%d = %d + %d\n",n,su[i],n-su[i]);
        }
    }
    return 0;
}