60分代码,改了快一个小时了

P1579 哥德巴赫猜想(升级版)

YuanZhizheng @ 2019-11-23 16:33:11

dalao们好 我的思路是,先拿一个数组a,将2到20000之间的所有质数都存起来。 然后方案中的第一个质数,是从最小的那个质数开始跑起来,方案中第三个质数是从最大的那个质数往下跑。然后找中间的那个质数。 因为第一个质数是从最小的质数开始跑,所以可以满足题目说的第一个质数最小的条件。 题目同时要求第一个质数相同且最小的时候,需要第二个质数最小,所以我将第三个质数从最大的往下跑,这样就能找到第一个质数相等且最小的时候,第二个质数最小的方案。

#include <bits/stdc++.h>
using namespace std;
int a[20005];
int main()
{
    int num1,num2,num3=1;
    for(num1=2; num1<20000; num1++)
    {
        int fl=0;
        for(num2=2; num2<=sqrt(num1); num2++)
        {
            if(num1%num2==0)
                fl=1;
        }
        if(fl==0)
        {
            a[num3]=num1;
            num3++;
        }
    }//将质数存起来
    int n,i,j,l;
    int flag3=0;
    cin>>n;
    int sum;
    for(i=1; i<=num3; i++)//第一个数从最小的跑
    {
        for(j=num3; j>=1; j--)//第三个数从最大
        {
            if(a[i]+a[j]>n)
                continue;
            int p=n-a[i]-a[j];//找第二个数
            int fff=0;
            for(l=1; l<=num3; l++)//判断质数
            {
                if(a[l]+a[j]+a[i]>20000)
                    break;
                if(a[l]==p)//若找到即可结束
                {
                    fff=1;
                    break;
                }
            }
            if(fff==1)
            {
                flag3=1;
                break;
            }
        }
        if(flag3==1)
            break;
    }
    printf("%d %d %d",a[i],n-a[i]-a[j],a[j]);
    return 0;
}

by suxxsfe @ 2019-11-23 17:04:13

你直接用f[i]表示i是否为质数,这样判断的时候方便也好查错


by YuanZhizheng @ 2019-11-23 17:28:39

@Thomas_Wade 谢谢,这样改完以后好解决了,已ac


by 为先 @ 2020-01-29 11:48:23

我居然是忘记把0筛掉了 啊啊啊啊啊 气死我了


|