algorithm - 求出一个小于1000的给定整数所需的素数最少

Question

这是我最近面临的编程挑战。
给你一个小于1000的数，你需要确定这个数和需要多少个最小的素数。
示例：

12: 2 (since 12=7+5)
14: 2  (since 14 = 7+7)

如果无法将给定的数拆分为素数和，则返回-1。
以下是一些测试用例：

88:2
117:3
374:2
363:3
11:1

Answer 1

简而言之：一个数的素数的最大数是3。因为只有168个素数小于1000，我们可以穷尽两个素数的组合，或者默认为3。通过使用一些额外的属性，我们可以很容易地找出元素的最小数目，甚至可以构造这些数目的集合。
我们可以解决这个问题，如果我们假设我们可以得到1000个素数的列表，其中有168个。
如果这个数是质数，那么显然答案是1。
对于非素数，我们必须找到不同的方法来解决这个问题。
Goldbach's conjecture [wiki]声明
大于2的偶数可以表示为两个素数之和。
这一猜想在一般情况下并没有得到证明，但至少知道对所有4×1018的数字都成立。
这意味着对于n = 2，答案是1，对于偶数n > 2，答案是2（因为只有一个偶数素数）。
在奇数和非素数的情况下，我们知道素数的最大数是3。实际上，因为如果我们从这个数中减去3，我们得到一个偶数，它可以由2或三个元素组成。显然这就是众所周知的：
大于5的整数可以写成三个素数的和。
我们唯一能改进上界的方法是找到两个素数的总和因此，这需要迭代所有的素数（最多1000个），并检查n-p是否也是素数然而，正如Goldbach's marginal conjecture [wiki]所说，我们只需减去2，因为这是唯一会产生奇数的偶数，因此是质数的候选者。
综上所述，基本上有以下几种情况：
当n<2时，不存在素数，因此明显失败；
对于一个素数，答案当然是一，因为我们可以简单地使用这个数；
对于大于2的偶数，我们可以使用Goldbach猜想，从而返回2，我们知道这是最小的，因为除了2，没有偶数素数；
对于大于2的奇数，我们知道如果n-2是素数，那么这个数就是2，因为2是素数，n-2是素数，我们知道没有更好的解，因为n不是素数；最后
对于n-2不是素数的奇数，我们知道n-3是偶数，根据goldbach猜想，我们可以构造三个素数的和。我们知道这是最优的，因为除了2没有其他素数，减法是偶数，因此我们可以再次使用Goldbach猜想。
因此，我们可以实现如下算法：

primes1000 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}

def min_prime(n):
    if n < 2:
        return -1
    if n in primes1000:
        return 1
    # 2 and 3 are prime numbers prime number
    # so all values here are > 3
    if n % 2 == 0:
        return 2    # Goldbach's conjecture, so 2
    if n-2 in primes1000:
        return 2
    return 3  # fallback on 3

例如：

>>> min_prime(12)
2
>>> min_prime(14)
2
>>> min_prime(88)
2
>>> min_prime(117)
3
>>> min_prime(374)
2
>>> min_prime(363)
3
>>> min_prime(11)
1

生成素数
我们可以使用相同的方法生成素数，例如：

def find_sum2(n):
    for p in primes1000:
        if n-p in primes1000:
            return (p, n-p)

def min_prime_tuple(n):
    if n < 2:
        return None
    if n in primes1000:
        return (n,)
    if n % 2 == 0:
        return find_sum2(n)
    if n-2 in primes1000:
        return (2, n-2)
    return (3, *find_sum2(n-3))

例如：

>>> min_prime_tuple(12)
(5, 7)
>>> min_prime_tuple(14)
(3, 11)
>>> min_prime_tuple(88)
(5, 83)
>>> min_prime_tuple(117)
(3, 5, 109)
>>> min_prime_tuple(374)
(7, 367)
>>> min_prime_tuple(363)
(3, 7, 353)
>>> min_prime_tuple(11)
(11,)

从迭代器大于n的那一刻起，我们就可以通过切断线性搜索来提高效率，但这通常不会有太大的区别，因为小于1000的素数非常少。
性能
因为n的上界是1000，所以没有大的oh。此外，如果n是无界的，我们不知道这个猜想是否仍然成立。
如果我们假设这个猜想成立，那么元组的生成是在O（g×c）中完成的，g是生成所有n个素数的时间，c是检查一个数是否是素数的时间。
如果我们在Python中对上述实现效率不高的方法进行基准测试，我们将实现以下基准测试：

>>> timeit(lambda: list(map(min_prime_tuple, range(0,1000))), number=10_000)
4.081021320000218

因此，这意味着，如果我们10000次构造1000以内的所有数字的元组，在2.70GHz的Intel（R）Core（TM）i7-7500U CPU上，这将在4.08秒内完成这意味着我们可以检查整个范围在408.1μs，或一个随机数大约0.408μs。