#define MAX 1000000
CGBitArray gba(MAX);
for (int i = 2; i < MAX / 2; i++)
for (int j = 2 * i; j < MAX; j += i)
gba.SetBit(j);
for (i = 1; i < MAX; i++)
if (!gba.GetBit(i))
printf("%d is primen", i);
And here’s the actual class:
class CGBitArray { public: void Init(int nStart, int nSize) { int nLen = nSize / 8; if (nSize & 0x07) nLen++; m_pData = new BYTE[nLen]; memset(m_pData, 0, nLen); m_nStart = nStart; m_nSize = nSize; m_nSet = 0; } CGBitArray(int nSize) { Init(0, nSize); } CGBitArray(int nStart, int nSize) { Init(nStart, nSize); } ~CGBitArray() { delete [] m_pData; } void SetBit(int nIndex, BOOL bSet = TRUE) { nIndex -= m_nStart; int nOffset = nIndex / 8; int nMask = (1 << (nIndex & 0x07)); BOOL bAlreadySet = m_pData[nOffset] & nMask; if (bSet) m_pData[nOffset] |= nMask; else m_pData[nOffset] &= ~nMask; if (bSet && !bAlreadySet) m_nSet++; else if (!bSet && bAlreadySet) m_nSet--; } BOOL GetBit(int nIndex) { nIndex -= m_nStart; return m_pData[nIndex / 8] & (1 << (nIndex & 0x07)); } BOOL& operator[](ULONG nIndex) { static BOOL bRet; return bRet = GetBit(nIndex); } int GetSize() { return m_nSize; } int GetStart() { return m_nStart; } int GetSetCount() { return m_nSet; } int GetClearCount() { return m_nSize - m_nSet; } protected: BYTE* m_pData; int m_nStart; int m_nSize; int m_nSet; };