输入一个不小于6的正整数n，将其拆分成三个素数之和，输出任意一解即可。

Question

#问题：
OJ上面时间超限，1804ms，本人大一cai狗，完全不知算法该如何优化了
#思路：
1.打好素数表
2.循环求拆分的三个素数
题目如下：

源代码如下：

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
vector<int>prime;
bool isPrime(int a)//进来的都是奇数
{
        int sq = sqrt(a);
        bool flag = true;
        for (int i = 3; i <= sq && flag; i += 2)
            if (a % i == 0)
                flag = false;
        return flag;
}
void f()
{
    prime.push_back(2);
    for (int i = 3; prime.back() <= 19999; i+=2)
    {
        if (isPrime(i))
            prime.push_back(i);
    }
}
int main()
{
    f();
    int a, i, j, k;
    while (cin >> a)
    {
        for (i = 0; i < prime.size() ; i++)
            for (j = 0; prime[j] < a-3 ; j++)
                for (k = 0; prime[k] < a-3; k++)
                {
                    if (prime[i] + prime[j] + prime[k] == a)
                    {
                        cout << prime[i] << " " << prime[j] << " " << prime[k] << endl;
                        goto aa;
                    }
                }
    aa:;
    }
    return 0;
}

恳求各路老爷们看看我吧！
感激万分！

Answer 1

不要搞第三个for循环了，第三个数就是a - prime[i] - prime[j]
再判断一下第三个数是不是素数就可以了