学步园

Prime Numbers

题目大意：给你一个区间，求出在这个区间内一共有多少个素数。2 <= a <= b <= 1000000

解题思路：

定义一个函数用来打出2-1000000之间的素数，把它放到数组中去，后面再接受区间，根据区间去统计素数表中的素数个数。

#include <stdio.h><br /> #include <stdlib.h><br /> #include <math.h></p> <p>void CompositeNumFilterV2(int n,int *flag);</p> <p>int flag[1000001];</p> <p>int main()<br /> {<br /> int count;<br /> int left,right;<br /> int NumOfTest;<br /> CompositeNumFilterV2(1000000,flag);<br /> register int i,j;<br /> while (scanf("%d",&NumOfTest)!=EOF)<br /> {<br /> for (j=0;j<NumOfTest;j++)<br /> {<br /> count = 0;<br /> scanf("%d%d",&left,&right);<br /> for (i=left;i<=right;i++)<br /> {<br /> if (flag[i] == 1)<br /> {<br /> count++;<br /> }<br /> }<br /> printf("%d/n",count);<br /> }<br /> }<br /> return 0;<br /> }</p> <p>void CompositeNumFilterV2(int n,int *flag)<br /> {<br /> int i, j;<br /> /*// 素数数量统计 */<br /> int count = 0;<br /> /* // 分配素数标记空间，明白+1原因了吧，因为浪费了一个flag[0] */<br /> /* //char* flag = (char*)malloc( n+1 ); */<br /> /* // 初始化素数标记，要高效点咯 */<br /> flag[2] = 1;<br /> /* // 注意是i<n不是上例中的i<=n了，理由自思 */<br /> for (i=3; i<n; i++)<br /> {<br /> flag[i++] = 1; /*// 偶数自然不是素数，直接置0好了 */<br /> flag[i] = 0;<br /> }<br /> /* // n为奇数 */<br /> if (n%2 != 0)<br /> {<br /> flag[n] = 1;<br /> }</p> <p> /*// 从3开始filter，因为2的倍数早在初始化时代就干掉了 */</p> <p> int k=sqrt(n);<br /> for (i=3; i <= k; i++)<br /> {<br /> /* // i是合数，请歇着吧，因为您的工作早有您的质因子代劳了 */<br /> if (0 == flag[i]) continue;<br /> /* // 从i的2倍开始过滤，变乘法为加法 */<br /> for (j=i; i*j <= n; j++)<br /> {<br /> flag[i*j] = 0;<br /> }<br /> }<br /> /*// 统计素数个数 */<br /> for (i=2; i<=n; i++)<br /> {<br /> if (flag[i]) count++;<br /> }<br /> /*<br /> //因输出费时，且和<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>核心相关不大，故略<br /> // 释放内存，别忘了传说中的内存泄漏<br /> //free(flag);<br /> return count;*/</p> <p>