Python实现：求数字乘积等于给定数的最小正整数

我来帮你搞定这个问题！要找到各位数字乘积等于给定x的最小正整数，核心思路是让数字的位数尽可能少，同时高位数字尽可能小，这样组成的数才是最小的。下面一步步拆解思路，再给出实现代码：

解题思路 #

• 特殊情况处理：
  • 如果x是1，直接返回1（因为1本身就是满足条件的最小数）
  • 如果x是0，返回10（这是最小的正整数，各位乘积为0；注意0不是正整数，所以不能返回0）
• 分解因子：
  • 我们要把x分解成个位数的乘积，而且要优先用大的个位数（从9到2遍历）。这么做的原因是：大的因子能减少数字的总位数（比如12分解成6×2是两位数，比分解成2×2×3的三位数更小）
  • 每次找到能整除x的个位数，就把它加入因子列表，然后将x除以这个数，重复直到不能整除为止
• 处理剩余质数：
  • 如果循环结束后x仍然大于1，说明x是一个大于9的质数（比如11），这时候只能把它作为单独的数字加入因子列表（因为没有更小的个位数能整除它）
• 生成最小数：
  • 把因子列表从小到大排序，拼接成字符串再转成整数。排序后高位数字更小，整个数自然是最小的（比如[6,2]排序后变成26，比62小）

实现代码 #

def product_x(x):
    # 处理特殊情况
    if x == 1:
        return 1
    if x == 0:
        return 10
    
    factors = []
    # 从9到2遍历，优先分解出大的个位数因子
    for i in range(9, 1, -1):
        while x % i == 0:
            factors.append(i)
            x = x // i
    
    # 如果剩下的x是大于9的质数，直接加入因子
    if x > 1:
        factors.append(x)
    
    # 排序后拼接成最小数字
    factors.sort()
    return int(''.join(map(str, factors)))

测试案例 #

• 当x=12时，函数返回26（2×6=12，且26是满足条件的最小数）
• 当x=18时，返回29（2×9=18，比36更小）
• 当x=11时，返回11（11是质数，没有更小的数满足乘积为11）
• 当x=0时，返回10（最小的正整数，各位乘积为0）

内容的提问来源于stack exchange，提问作者bb ef