# BitMap solution to save some space(JAVA)

• Each bit mark one number. Initial set all bit to be '1'.

Modify '1' to '0' if the number has been browsed.

``````public class Solution {
public int countPrimes(int n) {
if(n <= 2){
return 0;
}

byte[] bitMap;
if(n % 8 == 0){
bitMap = new byte[n / 8];
}
else{
bitMap = new byte[n / 8 + 1];
}
//set all bits to be '1'
for(int i = 0; i < bitMap.length; i++){
bitMap[i] = -1;
}

int result = 0;
//start from 2 to n
for(int i = 2; i < n; i++){
int index = (i - 1) / 8;
int indexBit = (i - 1) % 8;
if(oneToZero(bitMap,index,indexBit)){
result ++;
int next = i + i;
while(next < n){
index = (next - 1) / 8;
indexBit = (next - 1) % 8;
oneToZero(bitMap,index,indexBit);
next += i;
}
}
}
return result;
}

public boolean oneToZero(byte[] bitMap, int index, int indexBit){
switch(indexBit){
case 0:
if((bitMap[index] & 0x80) != 0){
bitMap[index] &= 0x7f;
return true;
}
else{
return false;
}
case 1:
if((bitMap[index] & 0x40) != 0){
bitMap[index] &= 0xbf;
return true;
}
else{
return false;
}
case 2:
if((bitMap[index] & 0x20) != 0){
bitMap[index] &= 0xdf;
return true;
}
else{
return false;
}
case 3:
if((bitMap[index] & 0x10) != 0){
bitMap[index] &= 0xef;
return true;
}
else{
return false;
}
case 4:
if((bitMap[index] & 0x08) != 0){
bitMap[index] &= 0xf7;
return true;
}
else{
return false;
}
case 5:
if((bitMap[index] & 0x04) != 0){
bitMap[index] &= 0xfb;
return true;
}
else{
return false;
}
case 6:
if((bitMap[index] & 0x02) != 0){
bitMap[index] &= 0xfd;
return true;
}
else{
return false;
}
case 7:
if((bitMap[index] & 0x01) != 0){
bitMap[index] &= 0xfe;
return true;
}
else{
return false;
}
}
return false;
}

}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.