找出数字乘积为 N 的最小数

我做了一个小函数来解决这个问题（如果输入的数字是任何质数的倍数（1、2、3、5、7 除外）——该函数将显示这个质数而不是答案）：

n = int(input())
def min_mult_num(n):
    if n == 0:
        return 10
    elif n < 10:
        return int('1' + str(n))
    else:
        n_mute = n
        list_help = []
        final_num = []
        for i in range(2,10):
            list_help.append(i)
        list_help = list_help[::-1]
        while len(str(n_mute)) > 1:
            for i in list_help:
                if n_mute%i == 0:
                    final_num.append(i)
                    n_mute = int(n_mute / i)
                    break
            else:
                return (f"Мы столкнулись с простым числом {n_mute}")
        final_num.append(n_mute)
        final_num = final_num[::-1]
        f = int(''.join((str(i) for i in final_num)))
        return f

min_mult_num(n) 

如果你需要根据功能逻辑解释一些东西，那么在这个答案的评论中写，我会尽量解释

我建议对内部循环进行一个小的合理化 - 提前终止，如果答案显然已经不起作用并且进一步转动循环是无用的：

        for j in range(len(i)):
            a*=int(i[j])
            if a == 0 or a > n:
                break

虽然有必要检查一下这是否会省钱。原则上应该是，因为数字比较操作非常便宜，但是将字符串解析为数字是非常昂贵的操作。乘法不是很昂贵。

但总的来说，问题显然需要在相反的方向上解决——从分解为因素。这应该快得多。

您的解决方案中存在几个缺陷。

1. if n == 0:不需要条件。n为自然数，不能为零。

2. 如果没有解决方案，等待答案的时间太长。没有答案的最小n是11。您正在运行99_999_999_999次迭代的循环。1000 亿很多。经验法则：现代计算机每秒执行大约十亿次基本运算。等 100 秒是可以的，但我们的操作也不简单。快速猜测表明您的程序在三秒钟内进行了一百万次迭代。它需要 100_000 倍以上。

3. 这不是你的错，而是问题条件的一个奇怪之处：为什么答案应该大于十？不清楚。现在，我将忽略此条件 - 我将寻找具有所需数字乘积的最小数字。

搜索候选人会自动提示，但并不总是最简单的解决方案就是最好的。让我们分析n = 18的例子。如果问题有解，则解的位数必须除以18。适合2 , 3 , 6 , 9。其中，您可以组合以下答案：18 \u003d 2 * 3 * 3 \u003d 2 * 9 \u003d 3 * 6。到因子的顺序为止，没有其他的组合。

让我们处理订单：2 * 9 = 9 * 2。等式得出两个解：29和92。我们需要更少：29。结论：数字中的数字一定不能减少。如果它们在某些地方减少，可以交换几个数字，并且可以获得具有相同产品的较小数字。

第二个观察：数字越少，数字越小：2 * 9 = 2 * 3 * 3。29 < 233。

那么算法是这样的：我们在除法的同时将n除以9，然后在数字的位数上从右到左写出9。然后我们转到8 - 我们在除法时写出八。我们继续前进，直到我们到达2。写出所有二进制数后，我们检查n = 1。如果不是，则n中有不能为数字的因子 - 没有答案。

该算法构建最短的数字（第二次观察）并且其中的数字不减少（第一次观察）。

如果答案是一位数，则在前面加一以满足问题中的“奇怪”条件：

n = int(input()) 
answer = []
for d in range(9, 1, -1):
    while n % d == 0:
        n //= d
        answer.append(str(d))
if n > 1: # n не является произведением чисел от 2 до 9
    print('No solution')
else:
    if len(answer) == 0: # это бывает если n = 1
        answer.append('1')
    if len(answer) == 1: # это бывает если n < 10
        answer.append('1')
    print(''.join(reversed(answer)))

$ echo 1 | python digits.py
11

$ echo 2 | python digits.py
12

$ echo 9 | python digits.py
19

$ echo 10 | python digits.py
25

$ echo 11 | python digits.py
No solution

$ echo 50 | python digits.py
255

$ echo 1000000000000 | python digits.py
5555555555558888