ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e552: 01210 - Sum of Consecutive Prime Numbers　解題心得

Not In My Back Yard | 2019-12-03 23:27:01 | 巴幣 0 | 人氣 295
題目連結：
題目大意：
給定一正整數 n （2 ≦ n ≦ 10000，當 n ＝ 0 時代表輸入結束），求 n 可以由多少種的連續質數和表示出來？

例如 53 可以表示為 53 （本身就是質數）或是 5 ＋ 7 ＋ 11 ＋ 13 ＋ 17 總共這兩種方式；而 20 則沒有這種組合。

範例輸入：
2
3
17
41
20
666
12
53
0
範例輸出：
1
1
2
3
0
0
1
2
解題思維：
先求出 2 ～ 10000 之間的所有質數，總共有 1233 個質數。

接著窮舉連續質數和的開頭，以 2 開頭、以 3 開頭、以 5 開頭等等，一直加上去。每加上一個數字，設現在總和為 S ，則代表 S 有這一組連續和，因此 S 的方法數要加 1 （用一陣列儲存總方法數）。

全部窮舉完後，接著每輸入一次 n ，就輸出對應的方法數即可。

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

創作回應

更多創作