超时怎么优化???

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

ebubu @ 2019-10-20 19:40:18

#include<iostream>
#include<math.h>
using namespace std;
bool panduang(int i)
{
    int b = 0;
    for (int a = 2; a <= pow(i, 0.5); a++)
    {
        if (i % a == 0)
        {
            return false;
            b++;
        }
    }
    if (b == 0)
    {
        return true;
    }

}
int main()
{
    int n;
    cin >> n;
    for (int i = 2; i < 20000; i++)
    {
        for (int j = 2; j < 20000; j++)
        {
            for (int k = 2; k < 20000; k++)
            {
                if((i+j+k)==n)
                {
                    while (panduang(i))
                    {
                        while (panduang(j))
                        {
                            while (panduang(k))
                            {
                                cout << i << " " << j << " " << k;
                                goto flag;
                            }
                            break;
                        }
                        break;
                    }
                }
            }
        }
    }
    flag:
    return 0;
}

by Hydrate @ 2019-10-20 19:46:16

@4833120nm 其实可以压掉两维的


by ebubu @ 2019-10-20 19:46:53

@北辰yama 怎么压,求助


by wmy_goes_to_thu @ 2019-10-20 19:49:45

@4833120nm 先枚举i,如果i不是质数直接下一个,再枚举j,同样判断质数,k肯定是n-i-j,判断k,判断质数可以筛法


by Hydrate @ 2019-10-20 19:51:38

@4833120nm

先判断n能否分解为{2, 2, n - 4}, 即n - 4是否为质数.

如果是, 输出

不是, 先输出3, 然后将n减去3, 按普通版做就行了


by ebubu @ 2019-10-20 19:58:37

@wangmaohua20090908 好的谢谢,明白了,非常感谢,成功了


by ebubu @ 2019-10-20 19:58:50

@北辰yama 谢谢!


|