查找 N 的四个因数,使乘积最大且和等于 N - Python 中的 Set-2

pythonserver side programmingprogramming更新于 2025/10/10 7:08:17

假设我们有一个数字 N;我们必须找到 N 的因数并仅返回 N 的四个因数的乘积,使得 −

  • 四个因数的总和与 N 相同。

  • 四个因数的乘积最大。

所有四个因数可以彼此相等以使乘积最大化。

因此,如果输入为 N = 60,则输出将为 50625,因为所有因数都是 → 1 2 3 4 5 6 10 12 15 20 30 60,它们的乘积为 50625,因为 15 已被选中四次,使乘积最大。

为了解决这个问题,我们将遵循以下步骤 −

  • my_map := a new map

  • v := a new list, v1 := a new list

  • 对于 i 在 1 到 (n) + 1 的平方根的上限范围内,执行

    • 如果 n mod i 等于 0,则

      • 在 v 的末尾插入 i

      • 如果 i 与 (n / i) 的整数部分不同,并且 i 不等于 1,然后

        • 在 v 的末尾插入 (n / i) 的整数部分

  • s := v 的大小

  • 最大值 := -1

  • map1 := 大小为 (n + 5) 的数组,用 0 填充

  • 对于范围从 0 到 s 的 i,执行

    • 对于范围从 i 到 s 的 j,执行

      • 如果 v[i] + v[j] < n ,然后

        • 在 v1 末尾插入 v[i] + v[j]

        • map1[v[i] + v[j]] := [v[i], v[j]]

        • my_map[v[i] + v[j]] := 1

  • s := v1 的大小

  • 对于 0 到 s 范围内的 i,执行

    • element := n - (v1[i])

    • 如果 element 在 my_map 中,则

      • a := map1[v1[i], 0]

      • b := map1[v1[i], 1]

      • c := map1[n - v1[i], 0]

      • d := map1[n - v1[i], 1]

      • 最大值 := a * b * c * d 的最大值,最大值

  • 如果最大值与 -1 相同,则

    • 显示"不可能"

  • 否则,

    • 显示最大值

示例

让我们看看下面的实现以便更好地理解 −

from math import sqrt, ceil, floor
def get_product(n):
   my_map = dict()
   v = []
   v1 = []
   for i in range(1,ceil(sqrt(n)) + 1):
   if (n % i == 0):
      v.append(i)
      if (i != (n // i) and i != 1):
         v.append(n // i)
   s = len(v)
   maximum = -1
   map1 = [0]*(n + 5)
   for i in range(s):
      for j in range(i, s):
         if (v[i] + v[j] < n):
            v1.append(v[i] + v[j])
            map1[v[i] + v[j]] =[v[i], v[j]]
            my_map[v[i] + v[j]] = 1
   s = len(v1)
   for i in range(s):
      element = n - (v1[i])
      if (element in my_map):
         a = map1[v1[i]][0]
         b = map1[v1[i]][1]
         c = map1[n - v1[i]][0]
         d = map1[n - v1[i]][1]
         maximum = max(a * b * c * d, maximum)
   if (maximum == -1):
      print("Not Possible")
   else :
      print("Maximum product", maximum)
n = 60
get_product(n)

输入

60

输出

Maximum product 50625

相关文章


有用资源