primes - 找到总和为给定值的最小质数

Question

我想找到总和为给定值的最小素数集，例如9 = 7 + 2(不是 3+3+3)。

我已经使用 sieve of eratosthens 生成了一个素数数组

我按降序遍历数组，以获得数组中小于或等于给定数字的最大素数。如果数字是奇数，这非常有效。但对于偶数则失败，例如 122 = 113 + 7 + 2 但 122 = 109 +13。

来自Golbach's Conjecture我们知道任何偶数都可以表示为两个素数的二和。因此，如果数字是偶数，我们可以直接返回 2 作为输出。

但我正在尝试找出一种除暴力之外的方法来找到最小素数。

Answer 1

虽然你的问题没有这么说，但我假设你正在寻找基数最小的素数集。

如果n是偶数，则按顺序考虑素数p，2,3,5,…；最终n - p将是素数，所以n是两个素数的和。这个过程通常收敛得非常快，两个素数中较小的一个很少大于 1000(而且通常比这个小得多)。

如果 n 为奇数，且 n - 2 为素数，则 n 为素数 2 与 n 之和 - 2.

如果 n 是奇数，并且 n - 2 不是素数，则 n - 3 是偶数，可以写成和两个素数，如上所述。

因此，您总能找到两个或三个素数，其总和等于任何目标n大于 3。