n131. p3. 質數切割法 - 高中生程式解題系統

內容

　　假設有一條木棒，長度為 $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$ ，代表需要切割的木棒的長度。

輸出說明

　　輸出最小的切割成本。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#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

提示：

標籤:

出處:

110 新北市資訊學科能力複賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
42044	s12270@kcis. ... (Ethan Chiu邱柏叡)	n131	C++ 解題思路	207	2024-09-22 15:14