主題

ZeroJudge - f711: 12218 - An Industrial Spy 解題心得

Not In My Back Yard | 2021-03-27 00:00:01 | 巴幣 0 | 人氣 40

題目連結:


題目大意:
輸入第一列給定一正整數 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;反之,則繼續窮舉下一個數字。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作