1.算法简介1.1筛法起源
筛法是一种简单检定素数的算法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛法（sieve of Eratosthenes）。
1.2筛法过程
具体做法是：给出要筛数值的范围 n，找出 以内的素数p1，p2，p3，……，pk。从最小素数2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去。
2.实现代码
代码为Linux平台，可简单修改移植到Windows。使用OpenMP实现简单的并行加速，有关OpenMP的用法，百度搜索“OpenMP简易教程”。
;uint32;uint64;inline void sieve(uint64 start,uint64 end,uint64& num,int threadNum){ assert(start>1); bool* a =new bool[end+1]; memset(a+2,true,end+1); #pragma omp parallel for num_threads(threadNum) for (uint64 i = 2; i <=(uint64)sqrt(end); i++) {if (a[i])for (uint64 j = i; i*j <= end; j++)a[i*j] = false; } uint64 prime_num=0; if(start==2)prime_num++; #pragma omp parallel for num_threads(threadNum) reduction(+: prime_num) for (uint64 i =(start%2==0?start+1:start); i <=end ;i += 2) {if (a[i])prime_num++; } num=prime_num; delete[] a;} int main(int argc,char* argv[]){if(argc!=4){fprintf(stderr, “usage: Eratosthenes start_number end_number threadNum\n”);exit(-1);}struct timeval ts,te;uint64 start=atoi(argv[1]);uint64 end=atoi(argv[2]);int threadNum=atoi(argv[3]);uint64 num=0;gettimeofday(&ts,NULL);sieve(start,end,num,threadNum);gettimeofday(&te,NULL);cout<<“count: “<<num<<endl;cout<<“total time: “<<((te.tv_sec-ts.tv_sec)*1000+(te.tv_usec-ts.tv_usec)/1000)<<“ms”<<endl;getchar();return 0;}参考文献
[1]百度百科-筛法
绊脚石乃是进身之阶。
