当前位置：文江博客话题详情

如何将一个数表示为4个素数之和？

发布于 2024-10-15 05:08:12 字数 552 浏览 9 评论 0原文

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

输入每行包含一个整数 N (N<=10000000)。这是您必须将其表示为四个素数之和的数字
示例输入：
24
36
46
示例输出：
3 11 3 7
3 7 13 13
11 11 17 7

我第一眼就想到了这个想法

查找 N 下面的所有素数
查找列表的长度 (.length = 4) 与整数分区问题 (Knapsack)

但复杂性非常糟糕对于这个算法我认为。这个问题也看起来像Goldbach's_conjecture 更多的。我该如何解决这个问题？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

霓裳挽歌倾城醉 2024-10-22 05:08:12

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

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

回复收藏 0 原文

深海夜未眠 2024-10-22 05:08:12

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

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

回复收藏 0 原文

幽蝶幻影 2024-10-22 05:08:12

您可以通过以下代码来实现它，通过将数字设置为常量 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;
}

You can implement it by the following code it save a lot of time in your program by make to digit as constant 2 & 2 or 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;
}

回复收藏 0 原文

~没有更多了~