代码之家  ›  专栏  ›  技术社区  ›  Charles Okwuagwu

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

  •  4
  • Charles Okwuagwu  · 技术社区  · 9 年前

    给定数字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\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的可能解集。

    我们是否可以添加其他巧妙的程序来进一步减少设置?

    2 回复  |  直到 9 年前
        1
  •  2
  •   Jaime    9 年前

    这与@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))
    
        2
  •  2
  •   Ralph M. Rickenbach    9 年前

    另一次暴力尝试:

    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)来知道这两个素数。