prime1.cpp

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

#include "iostream"
#include "math.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 CacheSieve(long n)
{
	long count = 0;
	long m = (long)sqrt((double)n);//m是窗口的大小
	bool *composite = new bool[n+1];
	memset(composite, 0, n);
	long *factor = new long[m];//每个索引即对应该数组一个值，该值为质数
	long *striker = new long[m];//存储的是窗口的大小范围内索引的值 
	long n_factor = 0;
	for (long i = 2; i <= m; ++i)
	{
		if (!composite[i])
		{
			++count;
			striker[n_factor] = Strike(composite, 2*i, i, m);
			factor[n_factor++] = i;
		}
	}

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