prime3.cpp

用Eratosthenes筛选算法,在1000000中求质数,分别用了串行算法,改进的串行算法,并行算法(openmp)实现,比较了执行时间

#include "iostream"
#include "math.h"
#include "omp.h"
#include "time.h"
#define M 100


using namespace std;

//用于数组的遍历，composite[]元素的个数是从2到n的数的个数，若为质数其值为false，反之为true
inline long Strike(bool composite[], long i,
				   long stride, long limit) 
{
	for (; i <= limit; i += stride)
	{
		composite[i] = true;
	}
	return i;
}

long ParallelSieve(long n)
{
	//count m *factor 为共享变量
	long count = 0;
	long m = (long)sqrt((double)n);//m是窗口的大小
	long *factor = new long[m];//每个索引即对应该数组一个值，该值为质数
//	long *striker = new long[m];//存储的是窗口的大小范围内索引的值 
	long n_factor = 0;
#pragma omp parallel
	{
		bool *composite = new bool[m+1];
		long *striker = new long[m];
#pragma omp single
		{
			memset(composite, 0, m);
			for (long i = 2; i <= m; ++i)
			{
				if (!composite[i])
				{
					++count;
					Strike(composite, 2*i, i, m);
					factor[n_factor++] = i;
				}
			}

		}
	long base = -1;

#pragma omp for reduction (+:count)
	for (long window = m+1; window <= n; window += m)
	{
		memset(composite, 0, m);
		if (base != window)
		{
			base = window;
			for (long k = 0; k < n_factor; ++k)
			{
				striker[k] = (base+factor[k]-1) / factor[k] * factor[k] - base;
			}
		}
		long limit = min(window+m-1, n) - base;
		for (long k = 0; k < n_factor; ++k)
		{
			//以上一窗口的索引为起点，遍历窗口大小为m的数组，
			striker[k] = Strike(composite, striker[k], 
				factor[k], limit) - m;
		}
		for (long i = 0; i <= limit; ++i)
		{
			if (!composite[i])
			{
				++count;
			}
			base += m;
		}
	}
	delete[] striker;
	delete[] composite;
	}
	delete[] factor;
	return count;
}
void main()
{
	/*cout<<"input number:"<<endl;
	int n;
	cin>>n;
	int count = ParallelSieve(n);
	cout<<count<<endl;*/
	
	int n = 100000000;
	clock_t start = clock();
	int count = ParallelSieve(n);
	clock_t final = clock();
	
	double end = ((double)final - (double)start)/1000 ;
	
	cout<<count<<endl;
	cout<<end<<endl;
}