在给定的一个数字下面找到两个质数的乘积最大值

Question

在给定的一个数字下面找到两个质数的乘积最大值

algorithmprimesmultiplication

4

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

我的（暴力）尝试：

1. 对于所有小于√N的质数P，找到列表{P，N/P}。 2. 找到一个质数Q的列表，使得Q在上面的列表中刚好小于N/P 。 3. 确定上述结果的最大乘积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\2} 这些值，其中 N\2 >= √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的可能解集。

还有其他聪明的程序可以添加以进一步缩小解集吗？

- Charles Okwuagwu

2

你在问题中提到了互质，但是你问的是“P和Q是质数吗？”。你需要质数还是互质？ - SureshS

3

这是一个已知的难题。如果你有效地解决了它，你就能破解RSA加密并变得富有和/或出名。 - n. m.

1

任何两个（非相等）质数总是互质的，这是多余的。那么，你禁止P*Q，其中P==Q吗？如果不是，那么标题中的“互质”必须去掉。 - Will Ness

1

@JohnColeman 可以允许 P 和 Q 相同。而且，没有“互质”这个词也是可以的。 - Will Ness

2

@CharlesO 因为这个方法按降序分解数字。因此，仅具有两个质因数的第一个数字是最大的。 :) - Will Ness

显示剩余18条评论

2个回答

2

这类似于@RalphMRickenback所描述的，但复杂度更紧密。

他所描述的素数查找算法是埃拉托色尼筛法，需要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))

- Jaime

1

实际上，该算法扫描阶段的时间复杂度是 O(pi n) = O(n / log n)，因为扫描的对象是小于 n 的质数而非小于 n 的正整数。您可以通过缓存质数来改进算法的运行时间。 - user448810

非常正确，已经编辑了，谢谢！对于O(n / log n)与更常见的复杂度如O(n^k)（其中0<k<1）相比较，有什么线索或参考资料吗？如果我记得我的L'Hospital定理正确的话，当n趋近于无穷大时，n^k / (n / log n)的极限为0，我认为这可以解释为，在渐进意义下，O(n / log n)并不比O(n)更好。这有任何意义吗？P.S.我喜欢你的网站，感谢你每周发布它，来自一个默默无闻的忠实读者！ - Jaime

@Jaime 埃拉托色尼筛法可以找到所有小于N/2的质数。我相信其中大部分质数可能会被丢弃。我们需要进一步受益于一个有效的“丢弃标准”，以限制被考虑的候选质数。 - Charles Okwuagwu

@Jaime：渐进地说，O(n / log n) 比 O(n) 更好。感谢你的赞美之词；也许你可以不时地贡献一些解决方案。甚至明天就可以。 - user448810

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ralph M. Rickenbach · Accepted Answer

另一种暴力尝试：

找到所有小于等于N/2的质数p
从最小的p开始迭代数组，只要p < √N并将其与最大的q < N/p相乘，保留最大的乘积。

如果有足够的内存（N/2位），可以制作一个该大小的位数组。将其初始化为全部为TRUE，但第一个位置除外。遍历位数组，计算当前位置的倍数并将所有倍数设置为false。如果下一个位置已经是false，则不需要重新计算其所有倍数，它们已经被设置为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;

第二步) 同样是小于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) 以知道这两个质数。