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

这与@RalphMRickenback所描述的相似,但具有更严格的复杂性界限。

他描述的主要查找算法是 sieve of Erathostenes ,它需要空间O(n),但具有时间复杂性O(n log log n),如果你想对此更加小心,你可能想看看维基百科上的讨论。

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

编辑 正如评论中提到的,素数扫描的时间复杂度优于线性 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))

另一次暴力尝试:

1. 查找所有素数p<=不适用于2
2. 只要p<√N,并将其与最大的q<N/p,保留最大的产品。

如果有足够的内存可用(N/2位),可以制作一个这样大小的位数组。用除第一个位置以外的所有TRUE初始化它。在位数组上迭代,计算所处位置的倍数,并将所有倍数设置为假。如果下一个位置已经为假,则不需要重新计算其所有倍数,它们已经设置为假。

因此,找到所有素数是<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)来知道这两个素数。