假設有一條木棒，長度為 $L$。如果我們能找到兩個質數 $M$ 及 $N$，使得 $L=M+N$，則我們可以使用「質數切割法」將它切成兩段，長度各自為 $M$ 及 $N$。所謂質數，是指在一個大於 1 的自然數中， 除了 $1$ 和此整數自身外，沒法被其他自然數整除的數，如 $2$、$3$、$5$、$7$、$11$、$13$、...。切割這一條木棒的成本是 $L$，也就是根據木棒的長度而定。我們可以把花費的成本當作把木棒搬上切割的工作台需要的成本(恰等於木棒長度)，木棒越長，要付給木工的錢就越多。而切割木棒的時候每次必定要使用「質數切割法」將它切成兩段，接著可將較短長度 $M$ 及 $N$ 的這兩條木棒繼續使用同樣方法。然而如果不滿足「質數切割法」的條件，則木棒就不能繼續切割下去，而其切割成本當然就是 $0$。
很顯然的，不同切割的 $M$ 及 $N$ 的選擇會有不同的成本。例如：如下圖所示，一根長度 $L=10$ 的木棒有下列兩種選擇：(甲) $L=M+N=3+7$ 或(乙) $L=M+N=5+5$。若選擇(甲) $L=M+N=3+7$ 的切割法，那長度為 $3$ 的木棒沒辦法再切割下去，而長度為 $7$ 的可再切割為 $2+5$，長度為 $5$ 的可再切割為 $2+3$。因此(甲)法的總切割成本為 $10+7+5=22$。
反之，若改採(乙) $L=M+N=5+5$ 的切割法，那長度為 5 的這兩根木棒各自可再切割為 $2+3$。因此(乙)法的總切割成本為 $10+5+5=20$。因此(乙)的切法這成本就是一個較好的選擇。
你的任務就是寫一支程式來找出切割一木棒所需最小的成本。
每筆測試資料只有一行，包含一個正整數，$1\leq L\leq 1000$，代表需要切割的木棒的長度。
輸出最小的切割成本。
10
20
5
5
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1K
公開 測資點#10 (5%): 2.0s , <1K
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <1K
公開 測資點#13 (5%): 2.0s , <1K
公開 測資點#14 (5%): 2.0s , <1K
公開 測資點#15 (5%): 2.0s , <1K
公開 測資點#16 (5%): 2.0s , <1K
公開 測資點#17 (5%): 2.0s , <1K
公開 測資點#18 (5%): 2.0s , <1K
公開 測資點#19 (5%): 2.0s , <1K
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 42044 |
|
n131 | 109 | 2024-09-22 15:14 |