prim.cpp

求n之内的素数

#include<iostream.h>
#include<fstream.h>
ifstream in("input.txt");
ofstream out("output.txt");
class bitset
{
public:
	bitset(int sz);
	int member(const int& x);
	void insert(const int& x);
	void Delete(const int& x);
private:
	int setsize;
	int arraysize;
	unsigned short *v;
	int arrayindex(const int& x)const;
	unsigned short bitmask(const int& x)const;
};
bitset::bitset(int sz)
{ 
		int i;
	setsize=sz;
	arraysize=(setsize+15)>>4;
	v=new unsigned short[arraysize];
	for(i=0;i<arraysize;i++)
		v[i]=0;
}
int bitset::arrayindex(const int& x)const
{
	return int (x)>>4;
}
unsigned short bitset::bitmask(const int& x)const
{
	return 1<<(int(x)&15);
}

int bitset::member(const int& x)
{
	return v[arrayindex(x)]&bitmask(x);
}
void bitset::insert(const int& x)
{
	v[arrayindex(x)]|=bitmask(x);
}
void bitset::Delete(const int &x)
{
	v[arrayindex(x)]&=~bitmask(x);
}
int main()
{
	int n,i,j;
	in>>n;
	bitset bt(n+1);
	for(i=0;i<=n;i++)
		bt.insert(i);

	for(i=2;i<=n;i++)
	{
		if(bt.member(i))
		{
			for(j=2*i;j<=n;j+=i)
				if(bt.member(j))
					bt.Delete(j);
		}
	}
	j=1;
	for(i=2;i<=n;i++)
		if(bt.member(i))
		{
			out<<i<<' ';
			if(j%10==0)
				out<<endl;
			j++;
		}
		return 0;
}