主題

ZeroJudge - f426: 高雄市109年資訊競賽國中組第四題 解題心得

Not In My Back Yard | 2020-11-23 00:00:01

題目連結:


題目大意:
輸入有兩列,第一列給定一正整數 N 、 第二列給定另一正整數 M (N ≦ M ≦ 10000),試問 N(含 ~ M(含)之間有多少個質數?這些質數的總和之值又是多少?



範例輸入:
範例輸入一:
1
20

範例輸入二:
5
17

範例輸入三:
9
14


範例輸出:
範例輸出一:
8
77

範例輸出二:
5
53

範例輸出三:
2
24


解題思維:
可以建質數表(如這題的作法),在建的同時(假設現在判斷的是數字 i)統計 1 ~ i 的質數數量(即目前質數表裡的質數數量)以及 1 ~ i 裡的質數總和。

當然,也是可以直接暴力對於 N ~ M 中每個數字都判斷是不是質數,然後統計個數以及總和。而建表的方式只是避免多餘、重複的計算而已,例如已知 2 是質數,之後就沒有必要再判斷 4 、 6 、…… 等數字是否為質數。




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

相關創作

更多創作