利用OpenMP实现埃拉托斯特尼(Eratosthenes)素数筛法并行化 分类: 算法与数据结构 2015-05-09 12:24 157人阅读 评论(0) 收藏
2024-10-16 11:34:44
1.算法简介
1.1筛法起源
筛法是一种简单检定素数的算法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛法(sieve of Eratosthenes)。
1.2筛法过程
具体做法是:给出要筛数值的范围 n,找出 n√以内的素数p1,p2,p3,……,pk。从最小素数2去筛,即把2留下,把2的倍数剔除掉;再用下一个素数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个素数5筛,把5留下,把5的倍数剔除掉;不断重复下去。
2.实现代码
代码为Linux平台,可简单修改移植到Windows。使用OpenMP实现简单的并行加速,有关OpenMP的用法,百度搜索“OpenMP简易教程”。
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <sys/time.h>
#include <cassert>
#include <omp.h>
using namespace std;
typedef unsigned int uint32;
typedef unsigned long long int 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]百度百科-筛法
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- python 查找指定内容的txt文件
- IIS7.5开启GZip压缩
- android 定制自己的日志工具
- 跨平台音乐播放器qmmp(Cross-Platform Audio Player Qmmp)
- JAVA多线程synchronized详解
- UIActinSheet和UIActionSheetDelegate
- shell中的替换
- poj 2565 Ants (KM+思维)
- 大端(Big Endian)与小端(Little Endian)
- python全栈学习--day8
- 初探linux子系统集之led子系统(一)
- 第5章 Linux上管理文件系统
- HADOOP HA 踩坑 - 所有 namenode 都是standby
- 【emWin】例程十二:FontCvt生成字库
- 【转】HTML5 API——无刷新更新地址 history.pushState/replaceState 方法
- assignment1SVM的一些经验
- ng-show和ng-if的区别
- Redis Python开发指南
- IE9 下 ellipsis bug fix
- 关于std::ios::sync_with_stdio(false)
热门文章
- 初试 Matlab 之去除水印
- Material Design风格的水波涟漪效果(Ripple Effect)的实现
- First Day
- oracle 语句 字段拼接(可换行)
- tiny_cnn 阅读(1)
- android 导入自己的生成的jar,老是 could not find class
- pagemap, from the userspace perspective
- eclise 部署web工程报 There are no resources that can be added or removed from the server.
- WinForm程序打包说明
- NSComparisonResul、NSNotFound、NSEnumerationOptions......的用处