找到小于给定数的 2 个素数的最大乘积

Question

给定一个数 N，我们如何找到最大 P*Q < N，使得 P 和 Q 是素数？

我的（暴力）尝试：

找到所有素数 P < √N
找到一个素数列表 Q，使得 Q 是正下方的最大素数 N/P 在上面的列表中
从上面确定最大乘积P*Q

虽然这种蛮力方法可行，但是否有针对此问题的正式（更明智的）解决方案？

示例：N=27

√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 < Q，那么我们有 Q >= √N。

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

我选择整数除法“\”，因为我们只对整数值感兴趣，而且整数除法确实比常规除法“/”快得多

问题简化为：

示例：N=27

√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

另一次暴力尝试：

找出所有素数 p <= N/2
从最小的p开始遍历数组，只要p < √N，再与最大的q相乘< N/p，保留最大的乘积。

如果有足够的可用内存（N/2 位），可以制作该大小的位数组。用除第一个位置之外的所有 TRUE 初始化它。迭代位数组，计算您所在位置的倍数并将所有倍数设置为 false。如果下一个位置已经是假的，你不需要重新计算它的所有倍数，它们已经设置为假。

因此找到所有素数 < O(N^2)。

a[1] := false;
m := n \ 2; // sizeof(a)
for i := 2 to m do
   a[i] := true;
for i := 2 to m do
   if a[i] then
     for j := 2*a[i] to m step a[i] do
       a[i*j] := false;

步骤 2) 也是 < O(n^2)：

result := 0;
for i := 2 to √N do
  if not a[i] then continue; // next i;
  for j := (n \ i) downto i do
     if not a[j] then continue; // next j
     if a[j] * a[i] < N
        result :=  max(result, a[j] * a[i]);
        break; // next i;
  if result = N then break; // you are finished

我想这可以进一步优化。可以保留(i,j)知道两个素数。

Answer 2

这与@RalphMRickenback 所描述的类似，但复杂性范围更严格。

他描述的找素数算法是sieve of Erathostenes，需要spaceO(n)，但是时间复杂度O(n log log n)，大家可以看看讨论在维基百科上，如果你想对此更加小心。

找到小于 n // 2 的素数列表后，您可以一次性扫描它，即具有 O(n) 复杂度，方法是让一个指针从开头开始，另一个在结尾。如果这两个素数的乘积大于您的值，请减少高指针。如果乘积较小，则将其与存储的最大乘积进行比较，并增加低指针。

EDIT 如评论中所述，素数扫描的时间复杂度优于 n 上的线性扫描，因为它仅在素数上较少比 n，所以 O(n / log 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))

找到小于给定数的 2 个素数的最大乘积

finding the maximum product of 2 primes below a given number

algorithm

primes

multiplication