d934. F. Lisa 的圍巾
http://zerojudge.tw/ShowProblem?problemid=d934
內容 ：
Gaspard (賈斯伯) 在一間人類學校就讀，為什麼要強調是人類學校呢，因為他的外形並不像人類！有人說他耳朵長長的好像兔子，但大部分的人都說他長得像隻小狗，總之他全身都毛茸茸的，毛的柔順質感讓大家都很喜歡他。
有一天，班上來了位轉學生名叫 Lisa (麗莎)，大家都跟 Gaspard 說「Lisa 和你長的好像喔！」「我哪有！」Gaspard 這樣回嘴。雖然這句話沒什麼諷刺的意味，但 Gaspard 聽了這句話心裡總是不大舒服。這一天早上，大家都將焦點放在 Lisa 上，沒什麼人跟 Gaspard 聊天，Gaspard 感覺一陣失落。
到了體育課，輪到 Gaspard 測跑步了，在老師的預備哨響後 Gaspard 衝了出去，沒想到在他旁邊的 Lisa 竟然也跟著他一起跑，而且跑的比他還快！Gaspard 終於忍不住了，一個早上的委屈和生氣就在這個時候爆發出來，Gaspard 去找 Lisa 打架了！
他們打了一陣之後，兩人相視而笑，他們是這問學校中，最特別的兩位呢！Lisa 和 Gaspard 交換圍巾後，就變成了很要好的朋友，一起聊天，一起用餐，遇到討厭的下雨天就一起玩耍，一起出餿主意！
事隔多年，Lisa 和 Gaspard 回想起他們的見面都還會因這段往事而笑呢！有一天他們又聊到他們相識的時候，他們交換圍巾的時候。Gaspard 對 Lisa 說：「你的圍巾真的很漂亮呢，而且又保暖！」Lisa 回應著說：「對啊，這可是我親自挑的。」Gaspard 突然很好奇，問道：「真的嗎，多少錢呀？」但 Lisa 只是笑而不答。在 Gaspard 的再三請求下，Lisa 終於給了 Gaspard 一個提示：「我有兩個數字 A 和 B ，把由 A 到 B 中不是質數的數字加起來，就是你現在戴的圍巾的價錢。」
這可真是傷腦筋，你能幫幫 Gaspard 嗎？
別忘了，質數就是那些正因數除了 1 以外只有自己的正整數，而且 1 不是質數喔！
輸入說明
：
第一行有一個整數 T (T ≤ 50000) ，代表接下來有幾組測試資料。每組測資皆只有一行，每行包含兩個整數 A 及 B (1 ≤ A ≤ B ≤ 7000)。
輸出說明
：
範例輸入 ：
5 4 6 2 6 1 6 4 4 5 5
範例輸出 ：
10 10 11 4 0
提示
：
出處
：
/**********************************************************************************/
/* Problem: d934 "F. Lisa 的圍巾" from 2010 NPSC 國中組初賽 */
/* Language: C */
/* Result: AC (42ms, 294KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-12 20:52:49 */
/**********************************************************************************/
#include<stdio.h>
int DP[7001] = {};
void Sieve_DP() {
DP[1] = 1;
int a, b;
char mark[7001] = {};
for(a = 2; a <= 7000; a++) {
DP[a] = DP[a-1];
if(mark[a] == 0) {
for(b = 2; a*b<= 7000; b++)
mark[a*b] = 1;
}
else DP[a] += a;
}
}
main() {
Sieve_DP();
int A, B, T;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &A, &B);
printf("%d\n", DP[B] - DP[A-1]);
}
return 0;
}
上一篇：d933. E. 傘兵
下一篇：b090. D. 正直DE