Morris' Blog

2011-06-01 22:07:57Morris

a121. 質數又來囉

內容：

你的好朋友質數先生又來找你囉，給你兩個數字，請算出這兩個數字包含的範圍內有幾個質數。

輸入說明：

輸入兩個正整數a,b(1<=a<=b<=100000000)。

保證b-a<=1000

輸出說明：

輸出一個非負整數，代表a到b之間(包含a,b)總共有幾個質數。

範例輸入： help

3 7
6 6
30 50

範例輸出：

3
0
5

提示：

出處：

(管理：VacationClub)

作法 : 暴力

/**********************************************************************************/
/* 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;
}

上一篇：a104. 排序

下一篇：d827. 買鉛筆