###### tags: `APCS`
# **d418－Product of digits**
### **題目連結：** [**d418**](https://zerojudge.tw/ShowProblem?problemid=d418)
### **題目解析**
這道題目要求我們找到一個最小的自然數 Q，使得 Q 中所有數字的乘積等於給定的數字 N。如果無法找到這樣的 Q，則返回 -1。這個問題實際上是將 N 分解為若干個 2 到 9 的因數，並將這些因數重新排列組合成一個最小的數字 Q。
### **解題方向**
1. 因數分解：我們需要將 N 分解為 2 到 9 的因數，因為這些因數才能組成一個自然數 Q 的每一位數字。
1. 最小化 Q：為了使 Q 最小，我們需要從最大的數字開始分解，這樣可以減少 Q 的位數。之後將分解出的因數排序並拼接成一個數字。
1. 檢查餘數：如果 N 無法完全被 2 到 9 的數字分解，則無法構成 Q，返回 -1。
### **程式解析**
1. 特殊情況處理：當 N 為 0 或 1 時，我們直接返回 N，因為 0 沒有任何因數，而 1 的 Q 也是 1。
1. 因數分解過程：我們從 9 到 2 依次檢查，看看 N 是否能被這些數字整除。能整除就將該數字加入因數列表，並將 N 除以這個數字更新，直到不能再被整除。
1. 最小化 Q：將因數列表排序後，我們拼接成一個最小的 Q。
1. 無法分解的情況：如果 N 無法完全分解為 2 到 9 的數字，那麼我們無法找到這樣的 Q，因此返回 -1。
### **完整程式碼**

def find_smallest_Q(N):
    if N == 0 or N == 1:
        return N
    
    factors = []
    for i in range(9, 1, -1):  # 從9開始檢查能否分解
        while N % i == 0:  # 當N能夠被i整除時，將i加入因數列表
            factors.append(i)
            N //= i  # 更新N
    
    if N > 1:
        return -1  # 如果N大於1，表示有剩餘因數不能被分解成2~9
    
    factors.sort()  # 排序因數列表，最小化Q
    Q = ''.join(map(str, factors))  # 將因數轉換為字串並拼接成一個數字
    return int(Q) if Q else -1  # 返回最小的Q，如果無法分解，返回-1