求给定数以下2个素数的最大乘积

Question

给定一个数N，我们如何求最大P*Q

null

√N = 5.196

Candidate primes: 2,3,5 --> [{2,13.5},{3,9},{5,5.4}] ->[{2,13},{3,7},{5,5}]

Solution: Max([2*13, 3*7, 5*5]) = 2*13 = 26

因此，暴力解决方案起作用。

再进一步，我们看到Q_max<=n/2，如果我们确实同意P =√n。

我们可以将我们的解决方案集细化为仅有那些值{P,n\2}，其中n\2>=√N。

√N = 5.196

Candidate P: 2,3 --> [{2,13},{3,9}] -->[{2,13},{3,7}]

(we drop {5,5} since N\P < √N i.e. 5 < 5.196)

Solution set: max([2*13, 3*7]) = 2*13 = 26

这可能看起来微不足道，但它只是消除了可能的解决方案集的1/3。

我们是否可以添加其他聪明的程序来进一步减少设置？

Answer 1

这与@RalphmRickenback描述的类似，但具有更严格的复杂性界限。

他描述的素数查找算法是Erathostenes的筛子，需要空间O(n)，但时间复杂度为O(n log log n)，如果你想对此更加小心，你可能想看看维基百科上的讨论。

在找到一个小于n//2的素数列表后，您可以通过将一个指针开始在开头，另一个指针结束来扫描它一次，即复杂度为O(n)。如果这两个素数的乘积大于你的值，减小高指针。如果乘积较小，则将其与存储的最大乘积进行比较，并增加低指针。

这里是Python的完整实现，而不是伪代码：

def prime_sieve(n):
    sieve = [False, False] + [True] * (n - 1)

    for num, is_prime in enumerate(sieve):
        if num * num > n:
            break
        if not is_prime:
            continue
        for not_a_prime in range(num * num, n + 1, num):
            sieve[not_a_prime] = False

    return [num for num, is_prime in enumerate(sieve) if is_prime]

def max_prime_product(n):
    primes = prime_sieve(n // 2)

    lo, hi = 0, len(primes) - 1
    max_prod = 0
    max_pair = None

    while lo <= hi:
        prod = primes[lo] * primes[hi]
        if prod <= n:
            if prod > max_prod:
                max_prod = prod
                max_pair = (primes[lo], primes[hi])
            lo += 1
        else:
            hi -= 1
    return max_prod, max_pair

在您的示例中，这将产生：

>>> max_prime_product(27)
(26, (2, 13))