prime.cpp

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

#include "iostream"
#include "math.h"


using namespace std;
inline long Strike(bool composite[], long i,
				   long stride, long limit) 
{
	for (; i <= limit; i += stride)
	{
		composite[i] = true;
		
	}
	return i;
}
long CacheUnSieve(long n)
{
	long count = 0;
	long m = (long)sqrt((double)n);
	bool* composite = new bool[n+1];
	memset(composite, 0, n);
	for (long i = 2; i <= m; ++i)
	{
		if (!composite[i])
		{
			++count;
			int count=Strike(composite, 2*i, i, n);
			cout<<count<<endl;
		}
	}
	for (long i = m+1; i <= n; ++i)
	{
		if (!composite[i])
		{
			++count;
		}
	}
	delete[] composite;
	return count;
}
void main()
{
	cout<<"input number:"<<endl;
	int n;
	cin>>n;
	int count = CacheUnSieve(n);
	cout<<count<<endl;
}