好素数问题505prim.cpp

设计一个算法

#include<iostream>
#include<fstream>
#include"time.h"
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
clock_t start,finish;
class BitSet
{
public:
	BitSet(int setsize);
	~BitSet(void);
	int Member(const &x);
	void Insert(const &x);
	void Delete(const &x);
	friend istream& operator>>(istream& istr,BitSet &x);
	friend ostream& operator<<(ostream& ostr,const BitSet &x);
private:
	int setsize;
	int arraysize;
	unsigned short *v;
	int ArrayIndex(const &x)const;
	unsigned short BitMask(const &x)const;
};
BitSet::BitSet(int sz):setsize(sz)
{
	arraysize=(setsize+15)>>4;
	v=new unsigned short[arraysize];
	if(v==NULL)throw;
	for(int i=0;i<arraysize;i++)v[i]=0;
}
BitSet::~BitSet(void)
{
	delete[]v;
}
int BitSet::Member(const &x)
{
	if(int (x)<0||int (x)>=setsize)throw;
	return v[ArrayIndex(x)]&BitMask(x);
}
int BitSet::ArrayIndex(const &x)const
{
	return int (x)>>4;
}
unsigned short BitSet::BitMask(const &x)const
{
	return 1<<(int (x) &15);
}
void BitSet::Insert(const &x)
{
	if(int (x)<0||int (x)>=setsize)throw;
	v[ArrayIndex(x)]|=BitMask(x);
}
void BitSet::Delete(const &x)
{
	if(int (x)<0||int (x)>=setsize)throw;
	v[ArrayIndex(x)]&=~BitMask(x);
}
int main()
{
	start=clock();

	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}

	int n;
	in>>n;
	if(n<=1)return 0;
	int count=0;
	int *pp=new int [n];
	BitSet sushu(n+1);
	int i,j;
	for(i=0;i<=n;i++)
		sushu.Insert(i);
	for(i=2;i<=n;i++)
	{
		if(sushu.Member(i))
		{
			count++;
			pp[count]=i;
		}
		for(j=2*i;j<=n;j=j+i)
			if(sushu.Member(j)==0);
			else
				sushu.Delete(j);
	}
	for(i=1;i<=count;i++)
	{
		out<<pp[i]<<' ';
		if(i%10==0)
			out<<endl;
	}
	finish=clock();
	cout<<finish-start;
	return 0;
}