#6、#10RE，求神犇看看

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

星河·莫 @ 2018-03-24 09:40:15

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,s[20000+5],gs,zs[20000+5],mai=2147483647,maj=2147483647,mak=2147483647;
int main()
{
    scanf("%d",&n);
    s[0]=s[1]=1;
    for (int i=2;i<=trunc(sqrt(n));i++)
    if (s[i]==0)
    for  (int j=i*2;j<=n;j+=i)
    s[j]=1;
    for (int i=2;i<=n;i++)
    if (s[i]==0)
    {
    gs++;
    zs[gs]=i;
    }
    for (int i=1;i<=gs;i++)
    for (int j=i;j<=gs;j++)
    for (int k=j;k<=gs;k++)
    {
    if (zs[i]+zs[j]+zs[k]==n)
    if (zs[i]<mai||zs[i]==mai&&zs[j]<maj||zs[i]==mai&&zs[j]==maj&&zs[k]<mak)
    {
    mai=zs[i];maj=zs[j];mak=zs[k];
    }
    }
    cout<<mai<<" "<<maj<<" "<<mak<<endl;
}

by da32s1da @ 2018-03-24 09:54:00

tle

输入19999，程序7s输出。。

by kitakami @ 2018-03-24 10:08:43

您的第三重循环可以删去

您的可以通过算出n-zx[i]-zs[j]的结果是不是质数来降低时间复杂度

by kitakami @ 2018-03-24 10:11:26

可以改成if(n-zs[i]-zs[j]==质数)

这样就不用枚举zs[k] 时间复杂度n^3→n^2

by da32s1da @ 2018-03-24 10:12:12

这是我的

#include<bits/stdc++.h>
using namespace std;
int n;
bool mak(int j)
{
    for(int i=3;i<=sqrt(j);i+=2)
    if(!(j%i)) return false;
    return true;
}
int main()
{
    cin>>n;
    if(mak(n-4)) printf("2 2 %d",n-4);
    else{
        cout<<3<<' ';n-=3;
        for(int i=3;i<=n;i+=2)
        if(mak(i)&&mak(n-i))
        {cout<<i<<' '<<n-i;break;}
    }

    return 0;
}