2011-06-01 22:07:57Morris
a121. 質數又來囉
http://zerojudge.tw/ShowProblem?problemid=a121
內容 ：
你的好朋友質數先生又來找你囉，給你兩個數字，請算出這兩個數字包含的範圍內有幾個質數。
輸入說明
：
輸入兩個正整數a,b(1<=a<=b<=100000000)。
保證b-a<=1000
輸出說明
：
輸出一個非負整數，代表a到b之間(包含a,b)總共有幾個質數。
範例輸入
：
3 7 6 6 30 50
範例輸出 ：
3 0 5
提示
：
出處
：
/**********************************************************************************/
/* Problem: a121 "質數又來囉" from */
/* Language: C */
/* Result: AC (216ms, 356KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-01 20:23:09 */
/**********************************************************************************/
#include<stdio.h>
#include<math.h>
int P[5200], pt = 0;
void P_Sieve() {
char mark[100000] = {};
int a, b;
P[pt++] = 2;
for(a = 3; a <= 10000; a += 2)
if(mark[a] == 0) {
P[pt++] = a;
for(b = 3; a*b <= 10000; b += 2)
mark[a*b] = 1;
}
}
int Judge(int N) {
if(N == 1) return 0;
register int a, sq = (int)sqrt(N);
for(a = 0; a < pt && P[a] <= sq; a++)
if(N%P[a] == 0) return 0;
return 1;
}
main() {
P_Sieve();
int A, B, a;
while(scanf("%d %d", &A, &B) == 2) {
int Ans = 0;
for(a = A; a <= B; a++)
Ans += Judge(a);
printf("%d\n", Ans);
}
return 0;
}
nice article