題目連結:
題目大意:
輸入第一列給定一正整數 C (1 ≦ C ≦ 200),代表有 C 筆測試資料,每筆佔一列。每列給定一個不超過 7 位數的數字(可能有前導 0),試問該數中挑出某些位數並加以排列而組成的數字種類之中,有多少為質數?
範例輸入:
4
17
1276543
9999999
011
範例輸出:
3
1336
0
2
解題思維:
總之先建立一個質數表(大小為 10000000,因為給定的數字最大不超過 7 位數),如
這題。
接著我們窮舉所有可能的排列組合,取 1 個位數、取 2 個位數等等,每種位數數量 K 下的每種 K 位數數字取法 P 再去判斷該數字 P 是否為質數(藉由以上的質數表)。
如果 P 是質數且沒有被列入過(因為計算的可形成的數字種類,所以我們需要避免重複計算到同一個質數),則所求數量 + 1;反之,則繼續窮舉下一個數字。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。