6

これが問題です（4つの素数の合計）は次のように述べています：

入力には、すべての行に 1 つの整数 N (N<=10000000) が含まれます。これは、4 つの素数の合計として表現する必要がある数です。

サンプル入力:
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 + 2 + "2 つの素数の合計" として表すことができます。

「2 つの素数の和」については、ゴールドバッハの予想を使用します。

于 2011-01-31T07:33:45.443 に答える
2

1,000 万以下の素数は約 70 万個あります。

数が偶数の場合はそれから 2 x 2 を減らし、奇数の場合はそれから 2 + 3 を減らします。ゴールドバッハの予想により、他の 2 つの素数を見つけることは難しくありません。

于 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 に答える