主題

ZeroJudge - d438: 10533 - Digit Primes 解題心得

Not In My Back Yard | 2021-03-08 00:00:07

題目連結:


題目大意:
輸入第一列給定一正整數 N (0 < N ≦ 500000),代表有 N 筆測試資料,每筆佔一列。每列給定兩正整數 t1 、 t2 (0 < t1 ≦ t2 ≦ 1000000),試問 t1(含) ~ t2(含)之間有多少個數字是位數質數(Digit Prime)?

一個整數 P 為位數質數的話,則滿足以下性質:
P 是質數、
P 的每位數之總和也為質數。

例如 41 為一位數質數,因為 41 是質數且 4 + 1 = 5 也是質數。



範例輸入:
3
10 20
10 100
100 10000


範例輸出:
1
10
576


解題思維:
先利用埃式篩法(如這題)將 ≦ 1000000 的質數全數找出。

然後再建立另一個列表 D,其中 D[i] 代表 1 ~ i 有多少個位數質數。

建完之後對於每筆輸入 t1 、 t2,D[t2] - D[t1 - 1] 即是所求。




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

創作回應

相關創作

更多創作