6

这是问题（四个素数的总和）指出：

输入的每一行都包含一个整数 N (N<=10000000)。这是您必须表示为四个素数之和的数字

样本输入：
24
36
46

样本输出：
3 11 3 7
3 7 13 13
11 11 17 7

第一眼就想到了这个想法

  • 找到 N 以下的所有素数
  • 使用整数分区问题（背包）查找列表的长度（.length = 4）

但我认为这种算法的复杂性非常糟糕。这个问题看起来也更像哥德巴赫的_猜想 。我怎么解决这个问题？

4

3 回答 3

9

这个问题有一个简单的技巧。您可以将所有数字表示为 3+2 +“两个素数之和”或 2 + 2 +“两个素数之和”，具体取决于数字的奇偶性。

对于“两个素数之和”，使用哥德巴赫猜想。

于 2011-01-31T07:33:45.443 回答
2

1000 万以下的素数大约有 70 万个。

如果数字是偶数减少 2 x 2，如果奇数减少 2 + 3，由于哥德巴赫猜想，找到其他两个素数并不困难。

于 2011-01-31T07:39:44.257 回答
0

您可以通过以下代码来实现它，通过将数字设为常量 2 & 2 或 2 & 3 可以在程序中节省大量时间：

int isPrime(int x) {
    int s = sqrt(x);
    for (int i = 2; i <= s; i++) {
        if (x % i == 0) {
            return 0;
        }
    }
    return 1;
}
void Num(int x, int & a, int & b) {
    for (int i = 2; i <= x / 2; i++) {
        if (isPrime(i) && isPrime(x - i)) {
            a = i;
            b = x - i;
            return;
        }
    }
}
int main() {
    int n;
    while (cin >> n) {
        if (n <= 7) {
            cout << "Impossible." << endl;
            continue;
        }
        if (n % 2 !=0) {
            int a, b;
            Num(n -5, a, b);
            cout << "2 3 " << a << " " << b << endl;
        }
        else {
            int a, b;
            Num(n -4, a, b);
            cout << "2 2 " << a << " " << b << endl;
        }
    }
    return 0;
}
于 2014-12-19T09:35:50.977 回答