代码哪里出错了，求助

P1579 哥德巴赫猜想（升级版）

Tiana天 @ 2018-03-24 23:32:06

本来用普通的打表~~（应该是打表）~~做的，发现wa了6，7，9三个点。然后翻了翻提交记录，发现绝大多数70分的人都是wa4,5,9三个点……

百思不得其解后，发现如果正确答案中有两个2，那么打表就是可行的，否则的话需要从3开始算…… 但是并不知道自己的第一个代码哪里错了，按理来说应该算完2发现不行之后就开始算3了啊…？

下面是第一个代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int p[20000];
int sushu=0;
void prime(){
    int flag=0;
    for(int i=2;i<=19999;i++)
    {
        flag=0;
        for(int j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                flag=10;
                j=i;
            }
        }
        if(flag==0)
        {
            sushu++;p[sushu]=i;
        }
    }
    return ;
}
bool isp(int num){
    for(int i=2;i*i<=num;i++)
    {
        if(num%i==0) return false;
    }
    return true;
}
int main(){
    scanf("%d",&n);
    prime();
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<n-p[i];j++)
        {
            if(n-p[i]-p[j]>=p[j])
            {
                if(isp((n-p[i]-p[j])))
                {
                    cout<<p[i]<<" "<<p[j]<<" "<<n-p[i]-p[j];
                    return 0;
                }
            }
        }
    }
    return 0;
}

by Tiana天 @ 2018-03-24 23:33:36

后来把n-p[i]-p[j]>=p[j]改成n-p[i]-p[j]>=2也不行……

by da32s1da @ 2018-03-25 07:01:00

看破

for(int i=1;i<=n;i++)
for(int j=i;j<n-p[i];j++)

这两个for错了！！

假如i=1,那么j=1,2,3,4,…,n-2。但是j应该是2,3,5,7,…再说i可能到n么？素数也没这么多。这是修改后的代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int p[20000];
int sushu=0;
void prime(){
    int flag=0;
    for(int i=2;i<=19999;i++)
    {
        flag=0;
        for(int j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                flag=10;
                j=i;
            }
        }
        if(flag==0)
        {
            sushu++;p[sushu]=i;
        }
    }
    return ;
}
bool isp(int num){
    for(int i=2;i*i<=num;i++)
    {
        if(num%i==0) return false;
    }
    return true;
}
int main(){
    scanf("%d",&n);
    prime();
    for(int i=1;i<=sushu;i++)
    {
        for(int j=i;j<sushu-i;j++)
        {
            if(n-p[i]-p[j]>=p[j])
            {
                if(isp((n-p[i]-p[j])))
                {
                    cout<<p[i]<<" "<<p[j]<<" "<<n-p[i]-p[j];
                    return 0;
                }
            }
        }
    }
    return 0;
}

by _LiM @ 2018-03-25 07:02:36

还是建议把筛法改成埃氏筛法吧，更直观一点

by _LiM @ 2018-03-25 07:06:54

还有如果能再剪枝的话，希望在跑i,j的时候给它们一个限定条件，在本例中就分别是p[i]<=n-4和p[i]+p[j]<=n-2。