主題
題目連結：
題目意譯：
回傳數字 1 ～ n 的排列方法數，其使得質數會排在質數索引值（從 1 開始算）上。
（回想一下，一個整數為質數若且唯若該數 > 1 且不能表示為兩個小於該數的正整數之乘積）
因為答案可能很大，所以將答案模 10 ^ 9 + 7 後回傳。
限制：
1 ≦ n ≦ 100
範例測資：
範例 1：
輸入： n = 5
輸出： 12
解釋： 例如 [1,2,5,4,3] 是一個合法排列，而 [5,2,3,4,1] 則不是因為質數數字 5 位於索引值 1。
範例 2：
輸入： n = 100
輸出： 682289015
解題思維：
我們定義 P[i] 為 1 ～ i 的所求方法數，而我們在建表的時候可以順便求出 P[i] 之值：
首先，將 P[i] 之值設為 P[i - 1] （P[0] = P[1] = 1）；
接著判斷完現在的數字 i 是否為質數。如果是，我們將 i 納入質數表後，此時將 P[i] 乘以質數表目前有的質數數量（記得取 10 ^ 9 + 7 的餘數）；如果不是質數，則將 P[i] 乘以 (i - 當前質數表質數數量) 取 10 ^ 9 + 7 之餘數。
這樣做便可以在建完質數表後，也一併求出 1 ≦ n ≦ 100 時的 P[n] 了。
而為何在計算 P[i] 時需要做以上操作呢？假設 1 ～ n 有 p 個質數，因此所求 P[n] 會是 p! × (n - p)! 。
因為質數固定在質數索引值上排列組合，而非質數則會在剩下的位置排列組合。
所以當 n 為質數時，P[n] 可以寫為
P[n - 1] × p
而當 n 不為質數時，P[n] 可以表為
P[n - 1] × (n - p)
而上面的遞迴式即是我們在建表時所寫的東西，因此本題也同時是一題典型的動態規劃（Dynamic Programming）之題型。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
