素数.cpp

在300秒左右求10的10次方以内的全部素数

/************************************************************************/
/* 求10的10次方以内的全部素数

实际所做的是10G以内的全部素数
	Author :　terence
	Data : 2007-11-1

	基本思想：
	首先求得1M以内的素数表，以后数据每1M分一段,仅研究该段的奇数数据,剔除这些数据当中
	是素数表内各素数的倍数值的数据,则剩下的都是素数.考虑到整数类型的变化(long , __int64),
	分两类进行处理,若一律采用__int64做处理，则影响效率。

	本程序未做素数输出打印处理。

	输出用时: 333s 

	配置：
	Pentium M 1.73G，RAM 1.28G
*/
/************************************************************************/
#define  PRINTPRIME 0//屏蔽素数输出打印处理

#include <iostream>
#include <cmath>

#include <Windows.h>


using namespace std;

typedef unsigned __int64 QWord;
typedef unsigned long LWord;

const size_t primeSize = 0x100000;
LWord g_nPrimeLength = 0;


LWord *g_pPrime = NULL;

inline size_t GetIndex(LWord n)
{
	return (n-3)>>1;

}

void FilterOnce(LWord * pDataBuf,LWord prime)
{
	LWord nMaxTimes = primeSize/prime;
	for(LWord i = 3;i<=nMaxTimes;i+=2)
		pDataBuf[GetIndex(i*prime)] = 0;

}

void InitPrePrime()
{
	if(g_nPrimeLength||g_pPrime)
		return;
	LWord * pDataBuf = new LWord[primeSize/2+1];
	//存取3以后的奇数
	for(LWord n =0;n<primeSize/2;n++)
		pDataBuf[n] = 2*n+3;
	//求出判定的上限奇数值的索引
	LWord maxI = (LWord)sqrt((float)primeSize + 3);
	maxI = GetIndex(maxI|1);
	//将素数的倍数值剔除
	for(LWord n = 0;n<= maxI;n++)
		if(pDataBuf[n])
			FilterOnce(pDataBuf,pDataBuf[n]);
	LWord * pPrime = new LWord[primeSize/2+1];
	LWord index = 0;
	for(LWord n =0;n<primeSize/2;n++)
		if(pDataBuf[n])
			pPrime[index++] = pDataBuf[n];
	g_nPrimeLength = index;
	g_pPrime = new LWord[g_nPrimeLength+10];
	//0x100000以内的素数值已经求得
	for(LWord n =0;n<g_nPrimeLength;n++)
		g_pPrime[n] = pPrime[n];
	delete pPrime;
	delete pDataBuf;

}
//一段所要处理的数据数,每段处理1M
const size_t nMDatBufLen = 0x100000/2;
//共处理的段数
const size_t nMSegment = 0x1000-1;//4G/1M

class Gen1MTo4G{
protected:
	LWord * m_pDataBuf;

public:
	Gen1MTo4G()
	{	
		m_pDataBuf = new LWord[nMDatBufLen+1];
	}
    virtual ~ Gen1MTo4G()
	{
		delete []m_pDataBuf;
	}
	void GenPrimProcess()
	{
		for(LWord i = 1;i<nMSegment;i++)
			GenPrimOnce(i);
	}
protected:
	void GenPrimOnce(LWord seg)
	{
		//求出该段始值
		LWord nBase = 0x100000*seg-1;

		cout<<"process: "<<nBase<<endl;
		//对该段做初始处理
		InitBuf(nBase,nMDatBufLen);
		//将奇数中的素数滤出
		FilterPrime();

		PrintPrime();
	}
	void InitBuf(LWord base,LWord len)
	{
		//得到这一段所有的奇数
		for( LWord n=0;n < len;n++)   	
			m_pDataBuf[n]   =   base + n *2;   

	}
	void FilterPrime()
	{
		//根据素数表中每个的值做循环
		for(LWord i = 0;i<g_nPrimeLength;i++)
			if(!FilterPOnce(g_pPrime[i]))break;
	}
	bool FilterPOnce(LWord prime)
	{
		LWord base = this->m_pDataBuf[0];
		LWord min = (base-1)/prime+1;
		LWord max = this->m_pDataBuf[nMDatBufLen-1]/prime;
		if(min<3)return false;
		for (;min<=max;min++)
		{
			this->m_pDataBuf[(prime*min-base)>>1] = 0;
		}
		return true;
	}
	void PrintPrime()
	{
#if defined (PRINTPRIME)&&PRINTPRIME

		for (LWord n = 0;n<nMDatBufLen;n++)
		{
			if(m_pDataBuf[n])
				cout<<m_pDataBuf[n]<<" ";
		}
#endif
	}

};
//每段的长度
const LWord nGDataBufLen  = 0x100000/2;
//要处理到的段数
const LWord nGSegment = 10*1024;

class Gen4GTo10G
{
protected:
	LWord * m_pDataBuf;
	LWord m_nSeg;
public:
	Gen4GTo10G()
		:m_nSeg(0x1000)
	{
		m_pDataBuf = new LWord [nGDataBufLen+1];
	}
	virtual ~Gen4GTo10G()
	{
		delete []m_pDataBuf;
	}
	void GenPrimeProcess()
	{
		while (m_nSeg<nGSegment)
		{
			GenPrimeOnce();
			++m_nSeg;
		}

	}
protected:
	//处理各段
	void GenPrimeOnce()
	{
		cout<<"process:"<<m_nSeg<<"M"<<endl;
		InitBuf(nGDataBufLen);
		FilterPrime();

		PrintPrime();
	}
	//初始化奇数
	void InitBuf(LWord len)
	{
		for(LWord n = 0;n<len;n++)
		{
			m_pDataBuf[n] = 2*n+1;
		}
	}
	void FilterPrime()
	{
		//根据素数表中每个的值做循环
		for (LWord n=0;n<g_nPrimeLength;n++)
		{
			if(!FilterPOnce(g_pPrime[n]))break;
		}
	}
	bool FilterPOnce(LWord prime)
	{
		QWord base  = QWord(this->m_nSeg) * QWord(0x100000);
		QWord min = (base-1)/prime+1;
		QWord max = (base+m_pDataBuf[nGDataBufLen-1])/prime;
		if(min<3)return false;
		for (;min<=max;min++)
		{
			this->m_pDataBuf[(prime*min-base)>>1] =0;
		}
		
		return true;
	}
	void PrintPrime()
	{
#if defined(PRINTPRIME)&&PRINTPRIME
		for(LWord i = 0;i<nGDataBufLen;i++)
			if(m_pDataBuf[i])
				cout<<m_pDataBuf[i]<<" ";
#endif
	}

};

void main()
{
	
	LWord nBegin = GetTickCount();
	//建立素数表
	InitPrePrime();
	//LWord nBegin = GetTickCount();
	//处理从1M到4G的数
	Gen1MTo4G * p1 = new Gen1MTo4G;
	p1->GenPrimProcess();
	delete p1;

	//处理从4G到10G的数
	Gen4GTo10G *p2 = new Gen4GTo10G;
	p2->GenPrimeProcess();
	delete p2;
	cout<<"Time used:"<<(GetTickCount()-nBegin)/1000<<"s"<<endl;

};

/************************************************************************/
/* 输出用时: 333s   
*/
/************************************************************************/